Sunday, June 5, 2011

WAP to Print All Possible Combination of Given Number From The Given Set "Only".

Given a set of numbers eg:{2,3,6,7,8}.Any one who is playing the game can score points only from this set using the numbers in that set. given a number, print all the possible ways of scoring that many points. Repetition of combinations are not allowed.
eg:
1. 6 points can be scored as
6
3+3
2+2+2

2. 7 can be scored as
7
2+2+3
but 2+3+2 and 3+2+2 is not allowed as they are repetitions of 2+2+3 & so on

3. 8 can be scored as
2+2+2+2
2+3+3
2+6
8

& so on

Algorithms is Pretty Clear if I understand the problem clear, i have already posted the same question with slight modification in which we are not restricted by array elements but we have to print all possible combinations without duplication such that
makes the given sum.

Algorithm

Here is What we do the same keep adding the array value into current-sum until it becomes equals to desired sum isn't it while checking array value is not equals to 0 (as zero don't counts in sum simple )& array values should be <= desired-sum so that we can get all combinations.& repeat the same process until we run out of array.


class PrintAllCombinations
{

public static void main(String[] args)
{
int s = 9;
//int[] a = new int[] {2,3,6,7,8};
int[] a = new int[] {2,3,6,7,8,0,10,66,45,3,56,89};
getCombinatsions(a, 0, s, 0, "");
}

static void getCombinatsions(int[] a, int j, int desiredSum, int currentSum, String st)
{
if(desiredSum == currentSum) {
System.out.println(st);
return;
}


if(currentSum > desiredSum)
{
return;
}



for(int i = j; i < a.length; i++)
{
if (a[i] <= desiredSum && a[i] != 0)
getCombinatsions(a, i, desiredSum, currentSum + a[i], st + "+" + a[i]);
else
break;
}
}


}


Time Complexity (N*2)
Space Complexity O(logn)
Run Here http://ideone.com/x2ICo

Suggestion/Comments are Welcome.??

2 comments :

Notting_Hill said...

hi shashank,

excellent blog..keep it up.

i have one question: isnt the time complexity exponential?

Shashank Mani said...

@Notting_Hill I think ist simple its DP problem can be solved in O(m*n)
where m is number of elements in array and n is value of the given number. what do u say.?