Print All Combinations of a Number as a Sum of Candidate Numbers

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)

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.)


A wordlock combination lock

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.

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 = 8

One 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.

VN:F [1.9.22_1171]
Rating: 2.9/5 (16 votes cast)
Print All Combinations of a Number as a Sum of Candidate Numbers, 2.9 out of 5 based on 16 ratings

35 thoughts on “Print All Combinations of a Number as a Sum of Candidate Numbers

  1. Anonymous

    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.

    VA:F [1.9.22_1171]
    0
  2. 1337c0d3r

    Yes, 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.

    VA:F [1.9.22_1171]
    +1
    1. Algoseekar

      hi 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.

      VA:F [1.9.22_1171]
      0
    2. shoudong

      The 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);
      }
      }

      }

      VN:F [1.9.22_1171]
      0
    3. Nathan

      I 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.

      VN:F [1.9.22_1171]
      +1
  3. Anonymous

    Thanks. 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.

    VA:F [1.9.22_1171]
    -1
  4. Anonymous

    The 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?

    VA:F [1.9.22_1171]
    +2
  5. Anonymous

    I 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.

    VA:F [1.9.22_1171]
    0
  6. Tracy

    I 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);

    VA:F [1.9.22_1171]
    +1
  7. Tracy

    By 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++;
    }

    VA:F [1.9.22_1171]
    0
    1. aimless

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

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

      VA:F [1.9.22_1171]
      0
    2. nirvanaforu

      I 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?

      VA:F [1.9.22_1171]
      0
  8. 1337c0d3r

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

    VA:F [1.9.22_1171]
    0
  9. WgpShashank

    HI 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

    VA:F [1.9.22_1171]
    0
  10. Tanin

    Your 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?

    VA:F [1.9.22_1171]
    0
  11. www

    i 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.

    VA:F [1.9.22_1171]
    0
    1. www

      the 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;
      }

      VA:F [1.9.22_1171]
      0
  12. Fox

    1337c0d3r:
    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

    VA:F [1.9.22_1171]
    0
    1. Liang

      If 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.

      VA:F [1.9.22_1171]
      0
  13. xuzuobing

    def 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]

    VA:F [1.9.22_1171]
    +1
  14. Dilip

    @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

    VA:F [1.9.22_1171]
    -2
  15. ashish

    this 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;
    }

    VA:F [1.9.22_1171]
    0
  16. LT

    Hi, 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);
    }

    }

    VN:F [1.9.22_1171]
    0
  17. Yi Yang

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

    VA:F [1.9.22_1171]
    0
  18. Pingback: leetcode: Combination Sum solution | 烟客旅人 sigmainfy

  19. sailorconan

    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

    VA:F [1.9.22_1171]
    0

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.

*