Combination Sum

Question

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

All numbers (including target) will be positive integers.
Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
The combinations themselves must be sorted in ascending order.
CombinationA > CombinationB iff (a1 > b1) OR (a1 = b1 AND a2 > b2) OR … (a1 = b1 AND a2 = b2 AND … ai = bi AND ai+1 > bi+1)
The solution set must not contain duplicate combinations.

Example, Given candidate set 2,3,6,7 and target 7, A solution set is:

[2, 2, 3] [7]

The solution code is :

class Solution {
    public:

    void doWork(vector<int> &candidates, int index, vector<int> &current, int currentSum, int target, vector<vector<int> > &ans) {
        if (currentSum > target) {
            return;
        }
        if (currentSum == target) {
            ans.push_back(current);
            return;
        }
        for (int i = index; i < candidates.size(); i++) {
            current.push_back(candidates[i]);
            currentSum += candidates[i];

            doWork(candidates, i, current, currentSum, target, ans);

            current.pop_back();
            currentSum -= candidates[i];
        }

    }

    vector<vector<int>> combinationSum(vector<int> &candidates, int target) {
        vector<int> current; 
        vector<vector<int> > ans;
        sort(candidates.begin(), candidates.end());
        vector<int> uniqueCandidates;
        for (int i = 0; i < candidates.size(); i++) {
            if (i == 0 || candidates[i] != candidates[i-1]) {
                uniqueCandidates.push_back(candidates[i]);
            }
        }
        doWork(uniqueCandidates, 0, current, 0, target, ans); 
        return ans;
    }
};

Now, while i can understand the solution by taking an example case, how can i myself come out with such a solution. The main work is going in this function :

    for (int i = index; i < candidates.size(); i++) {
        current.push_back(candidates[i]);
        currentSum += candidates[i];

        doWork(candidates, i, current, currentSum, target, ans);

        current.pop_back();
        currentSum -= candidates[i];
    }

Please tell me how to comprehend the above code and how to think that solution. I can solve basic recursion problems but these look out of reach. Thanks for your time.

Answer 1

So what the code basically does is:

1. Sort the given set of numbers in increasing order.
2. Remove duplicates from the set.
3. For each number in the set:
   • Keep adding the same number, until the sum is either larger or equal to the target.
   • If it is equal, save the combination.
   • If it is larger, remove the lastly added number (go back to the previous step) and start adding the next number in the set to the sum.

For understanding recursion, I like to start with very simple cases. Let's see for example: Candidates: { 2, 2, 1 } Target: 4

Sorting and removing the duplicates changes the set to { 1, 2 }. The sequence of recursion will be:

• Sum = 1;
  • Sum = 1 + 1;
    • Sum = 1 + 1 + 1;
      • Sum = 1 + 1 + 1 + 1; (Same as target, save the combination)
      • Sum = 1 + 1 + 1 + 2; (Larger than target, no more number to add)
    • Sum = 1 + 1 + 2; (Save the combination, no more number to add)
  • Sum = 1 + 2;
    • Sum = 1 + 2 + 2; (Larger, no more number)
• Sum = 2;
  • Sum = 2 + 2; (Save, this is the last recursion)