Source

Problem

Given a target number, and a series of candidate numbers, print out all combinations, so that the sum of candidate numbers equals to the target.

Here order is not important, so don’t print the duplicated combination.

e.g. target is 7, candidate is 2,3,6,7
output should be 7 and 3+2+2 (but not print 2+3+2, 2+2+3)

My Attempt

Sum(int arr[], int remainder, int index, int visited[])

{

if (index LessThen 0 ) { return; }

if (difference == 0) {

// bingo!

printAddition(arr, visited); // print all visited numbers

return;

}

if (difference - arr[index] > = 0 ) {

visited[index]++;

Sum(arr[], difference - arr[index], index, visited[]); // repeat the number dont move index

Sum(arr[], difference - arr[index], index - 1, visited[]);

visited[index]--;

}

Modified Problem

Let’s change the question a little bit.

Find all possible combination of numbers using a pre-defined candidate set.
Each number from the candidate set may be used only once in the combination.

For example,

Candidate Set = {10, 1, 2, 7, 6, 1, 5}
Target Number = 8

One possible output could be:
1+1+6
1+2+5
1+7
2+6