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 :

hi shashank,

excellent blog..keep it up.

i have one question: isnt the time complexity exponential?

@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.?

Post a Comment