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 is2,3,6,7

output should be7and3+2+2(but not print2+3+2,2+2+3)

Please note that the same repeated number may be chosen from the candidate set. We may also assume that the candidate set does not contain duplicate numbers, as this will be redundant. We assume all numbers will be positive integers, I will explain why this assumption is important for obtaining a solution later.

**Hint:**

Think about how to avoid printing duplicates. Think about developing a systematic method to search all possible solutions. How do you determine the condition that ends the search? (**Note:** Thanks to a kind reader who pointed out that *sorting the numbers *is not necessary for removing duplicates, as indicated in my previous version of this post.)

**Solution:**

To search for all combination, we use a backtracking algorithm. Here, we use the above example of candidate=**{2,3,6,7}** and target=**7**.

First, we start with a sum of **0**. Then, we iterate over all possibilities that can be added to sum, which yields the possible set of sum=**{2,3,6,7}**. Assume now that sum=**2**, we continue adding all possible candidate numbers **{2,3,6,7}** to sum=**2**, which yields sum=**{4,5,8,9}**. Each step we have to use an array to keep track of all the indices of candidate numbers that add to the current sum, so that we can print the combination later. The next case would be sum=**3**. We look at all possible candidate numbers **{3,6,7**} to be added to sum=**3**, which yields sum=**{6,9,10}**. Note that there is no need to look backward (ie, candidate numbers that are smaller than **3**), as this would only yield duplicate results. We keep doing this recursively, until we reach the conditions below, where we stop.

We stop when the sum is *greater *than the target sum. Why? Remember our earlier assumption that candidate numbers must *all be positive*? Since the candidate array contains only *positive numbers*, if we continue searching, we would only add larger numbers to the sum, and this would not help us achieving the target sum. The other case where we stop is when the sum is *equal *to the target sum. Hooray! We have found a valid combination.

If the candidate array contains both positive and negative numbers, is there a condition to end the search? To answer this question, think of this example where you could add up to a very large positive number (with repeated sum of positive numbers) and then repeatedly subtract down to a very small number. There would be infinitely number of combinations that can be found, and yet searching could not be stopped with an ending condition.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
void printSum(int candidates[], int index[], int n) { for (int i = 1; i <= n; i++) cout << candidates[index[i]] << ((i == n) ? "" : "+"); cout << endl; } void solve(int target, int sum, int candidates[], int sz, int index[], int n) { if (sum > target) return; if (sum == target) printSum(candidates, index, n); for (int i = index[n]; i < sz; i++) { index[n+1] = i; solve(target, sum + candidates[i], candidates, sz, index, n+1); } } void solve(int target, int candidates[], int sz) { int index[10000]; index[0] = 0; solve(target, 0, candidates, sz, index, 0); } |

**Further Thoughts:**

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 =8One possible output could be:

1+1+6

1+2+5

1+7

2+6

This question is left as an exercise. You should be able to solve this problem with little modification to the previous algorithm.

The UVa Online Judge website has this same problem called Problem 574 – Sum It Up. If you don’t know about the UVa Online Judge, it is a website I *highly recommended*. It has tons of programming problems (ranging from easy to difficult) to practice. You may also submit your code to their server, which the machine will run your program against their secret input and automatically judge if your solution is correct.

hello, the exercise you left is actually a subset-sum problem.

I modified the program index[n]->index[n]+1, it seems it works. But I found I missed "1+1+6" this case. Can you explain a little bit for better understanding, especially about the index[] array ? Thanks.

0Yes, it is a subset-sum problem. The sole purpose of the index array is to keep track of the candidate numbers' indices that's been selected, so that we can print them out later when we found a solution.

For example, if the candidate set = {2,3,6,7}, and one of the solution set is "2+2+3", then index[0]=0, index[1]=0, index[2]=1.

+1hi ihas1337 code,

i have doubt that how your neglecting the duplicates combination that make same targate number

e.g first 2+2+3 is right

but how ur program is not not print 2,3,2, & 3,2,2, plz explain..i m sure i m missing sumthing so plz explain this issue..

Thanks its Gr8 Program & Explanation

Please REPLY ASAP.

0The index array is actually a good idea, but we don’t necessary use it. Following is my algorithm:

public static boolean contains(int[] arr, int value){

for(int i=0; i < arr.length; i++){

if(arr[i] == value) return true;

}

return false;

}

public static void printArray(int[] arr, int sz){

for(int i = 0; i< sz; i++){

System.out.print(arr[i] + ", ");

}

System.out.println();

}

public static void printComposition(int[] value, int[] retSet, int sz, int target, int preValue){

if(target < 0) return;

if(target == 0){

printArray(retSet, sz);

return;

}

for(int i = preValue; i<= MAX_VALUE && i <= target ; i++){

if(contains(value, i)){

retSet[sz] = i;

printComposition(value, retSet, sz + 1, target – retSet[sz], i);

}

}

}

0I have a quick question about your solution for the original problem.

You said that “… The next case would be sum=3. We look at all possible candidate numbers {3,6,7} to be added to sum=3, which yields sum={6,9,10}. Note that there is no need to look backward (ie, candidate numbers that are smaller than 3), as this would only yield duplicate results.”

I don’t quite understand why you do not add the candidate number 2 to the sum = 3. Suppose the case where target = 6 (instead of 7). Then your method will miss the combination 2+2+2 in this case.

+1Thanks. If the solution was "2+2+3", then index[1]=0, index[2]=0, index[3]=1.

I used the modification of "index[n]->index[n]+1" and "add one more element(0) to this array" to check some tests and found it correct unless some redundant element in the array. This is what I tried following your explanation but still could not work out this EASY exercise. so can you tell me the solution for me to have a better understanding of it or can you tell me any good reference ? Thank you very much.

-1The second part says that we have to use a number only once,how do you explain your output of 1,1,6 in this case?

+2There are two 1's in the candidate set.

+2For the exercise problem, any hint how to avoid redundancy in the output?

0I got the solution. For those who have questions about the exercise problem, here are some hints.

1) sorting

2) when doing the loop in the array, check current number, if it is the same as the previous one, skip it.

These two hints can avoid redundancy.

Hi ihas1337code, thanks for this post. Now I got better understanding of this kind of questions which can be solved by backtracking technique.

0I think there should be a return after print the current combination, since there is no need to proceed given that the sum is already equal to the target.

if (sum == target)

printSum(candidates, index, n);

+1By the way, I think use a vector instead of a index array can save a lot of space, if it is an issue…

E.g, for the exercise problem:

for (int i = startIdx ; i < candidates.size() ; i++)

{

v.push_back(candidates[i]);

combinationsOfSumNoRepeat(targetSum,candidates,v,i + 1,partialSum + candidates[i]);

v.pop_back();

while (candidates[i + 1] == candidates[i])

i++;

}

0@Tracy:

Do you also intend to sort the inputs? I thought as you have a loop:

while (candidates[i + 1] == candidates[i])

i++;

0I think he/she did sort it beforehand.

0I dont understand this part either,

while (candidates[i + 1] == candidates[i])

i++;

I dont think it’s useful here. However, as I tested with the exercise, the results look like:

1+7

7+1

both will show up, because the 2nd 1 and 7 will be a pair, and then 7 and the 6th 1 will be pair for the sum again, is there a way to avoid this kind of duplication?

0@Tracy:

Yup, you're right. Adding a return statement is better after the sum reaches the target.

And yup, I believe your solution is correct for the exercise problem.

0its toughest program i have ever seen plz explain more deeply how the control is transferring..??

0HI Geeks Plz Find The Working Code the Same & Let me Know if Anything Missing

#define MAX_POINT 4

#define ARR_SIZE 100

#include

/* Utility function to print array arr[] */

void printArray(int arr[], int arr_size);

/* The function prints all combinations of numbers 1, 2, …MAX_POINT

that sum up to n.

i is used in recursion keep track of index in arr[] where next

element is to be added. Initital value of i must be passed as 0 */

void printCompositions(int n, int i)

{

/* array must be static as we want to keep track

of values stored in arr[] using current calls of

printCompositions() in function call stack*/

static int arr[ARR_SIZE];

if (n == 0)

{

printArray(arr, i);

}

else if(n > 0)

{

int k;

for (k = 1; k <= MAX_POINT; k++)

{

arr[i]= k;

printCompositions(n-k, i+1);

}

}

}

/* UTILITY FUNCTIONS */

/* Utility function to print array arr[] */

void printArray(int arr[], int arr_size)

{

int i,flag=1;

for (i = 0; i arr[i+1]) flag=0;

if(flag)

for (i = 0; i < arr_size; i++)

printf("%d ", arr[i]);

printf("\n");

}

/* Driver function to test above functions */

int main()

{

int n = 5;

printf("Differnt compositions formed by 1, 2 and 3 of %d are\n", n);

printCompositions(n, 0);

getchar();

return 0;

}

Run here https://ideone.com/shIbo

0Your solution takes O(2^n).

I come up with a dynamic programming approach, which takes O(T*n*n), T=target number, n=the size of the number set.

I define d[s][i] = [ [a0, a1, …, ai-1], [b0, …, bi-1], and so on] that a0 + a1 +… + ai-1 = s, b0 + b1 + … + bi-1 = s

It would take O(s*n) memory though.

Is my solution correct?

0i think it is similar as the problem 8.7 in Cracking the coding interview(4th edition).

Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent), write code to calculate the number of ways of representing n cents.

0the solution to 8.7 problem is something like below, we can easily adapt to this problem

int F(int n,int div){

if(n==0)

return 0;

int next_div;

switch(div){

case 25:

next_div = 10;

break;

case 10:

next_div = 5;

break;

case 5:

next_div = 1;

break;

case 1:

return 1;

}

int ways = 0;

for(int i=0;i*div <=n;i++)

ways+=F(n-i*div,next_div);

return ways;

}

01337c0d3r:

Some questions about exercise. You said that every number may be used only once in the combination, what about two “1” in the candidate set? If they are considered as different numbers, we should get the following output:

1+6+1

1+2+5

1+7

2+6

2+1+5

7+1

but you output is:

1+1+6

1+2+5

1+7

2+6

What does your algorithm output for the following combination?

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

Target Number = 8

0What is the complexity of the above algorithm?

0I think it is 2^n. Any other ideas?

+1If target is very large but the values of each candidates scatter, then the algorithm will be O(2^n), as general subset sum problem is NP-Complete.

0For exercises:

Change two places:

index[n+1] = i; ==> index[n+1] = i+1;

cout << candidates[index[i]] < cout << candidates[index[i]-1] << ((i == n) ? "" : "+");

0def combination_sum(candidates, target):

sorted_candidates = sorted(candidates, reverse=True)

results = []

target_sum(sorted_candidates, target, results)

def target_sum(candidates, target, results):

if target == 0:

print results

return

for idx, candidate in enumerate(candidates):

if candidate > target:

continue

else:

results.append(candidate)

target_sum(candidates[idx:], target – candidate, results)

del results[-1]

+1@1337c0d3r : Cant we also use BFS to solve this problem. I tried using that approach, but the online judge rejected the large solution because time limit exceeded.

My approach is basically,

0 –> has 4 children, {2,3,6,7}

2 –> has 4 children {4,5,8,9}

3 –> has 4 children {5,6,9,10}

Whenever the value of a child is greater than the target, it is dropped.

Let me know if this is an acceptable approach for an interview question

-2this much code is enough simple n concise

void printSum(int index[], int n) {

for (int i = 0; i < n; i++)

cout << index[i] << " ";

cout < target)

return;

if (sum == target)

printSum(index, n);

for (int i = st; i <= end; i++) {

index[n] = candidates[i];

solve(target, sum + candidates[i], candidates, i,end, index, n+1);

}

}

int main() {

// Start typing your code here…

cout << "Hello world!" << endl;

int index[10000] ={0};

int st=0;

int end =4;

int candidates[5] ={2,3,1,6,7};

int target =7;

solve(target, 0, candidates, st,end,index,0);

return 0;

}

0I think the answer of online judge is wrong. It is still the version which sorts the candidates array first.

0Hi, guys, I code in Java below, but it does not work. I guess the problem on the “path” but I do not know how to correct it. Anyone could give me help?Thanks.

import java.util.ArrayList;

public class AllCombinationOfANumber {

private ArrayList<ArrayList> results = new ArrayList<ArrayList>();

public ArrayList<ArrayList> getCombinations(int target, int[] candidates) {

ArrayList path = new ArrayList();

this.solve(target, candidates, 0, 0, path);

return results;

}

private void solve(int target, int[] candidates, int sum, int index, ArrayList path) {

if (sum > target)

return;

if (sum == target)

this.results.add(path);

for (int i = index; i < candidates.length; i++) {

path.add(candidates[i]);

solve(target, candidates, sum + candidates[i], i, path);

}

}

0Hi,

Could you explain what the variable sz means in your code?

Thanks

0The example works but to me it’s quite hard to understand. Here is my solution using tree to store all the possibilities and solutions:

0Pingback: leetcode: Combination Sum solution | 烟客旅人 sigmainfy

private static void find(int target, int[] arr) {

helper(arr, target, new Stack());

}

private static void helper(int[] arr, int target,Stack result) {

if(target==0){

System.out.println(result);

}else if(target<0){

return;

}

for(int i=0;i<arr.length;++i){

result.add(arr[i]);

helper(arr,target-arr[i],result);

result.pop();

}

}

remove duplicate

0Can u do this program without recursion , i think u will not be able to do so

0