Combination Sum I

Given asetof candidate numbers (C)(without duplicates)and a target number (T), find all unique combinations inCwhere the candidate numbers sums toT.

Thesamerepeated number may be chosen fromCunlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

For example, given candidate set[2, 3, 6, 7]and target7,
A solution set is:

[
  [7],
  [2, 2, 3]
]

Brainstorm

It may be interesting to start from a base case: if [7] = 7, then obviously we return. More generally, if the array itself has a sum equal to the target, then return.

How can we reduce any instance of the problem to this base case? Well, consider [2, 2, 3]. How do we know which numbers to add after each one? Starting from 2, we know that to get 7, the next few numbers must add up to 5. We then added 2 again, and now the next few numbers must add up to 3...which is exactly what our last number is!

Notice that at each instance, we can deduce which target the remaining numbers must sum up to. Isn't this the equivalent of another subproblem? In the case of the example, it's like we're combining solving two problems: one with target 2, and one with target 5. The one with target 5 is then split into finding numbers to add up to 2 and to 3, and so on. This calls for recursion.

Of course, how would we know at each step that the number we added is correct? Unfortunately we have no clue at that point. But we will once we hit a point in the recursion stack when the numbers do not sum up to the target. We just have to be able to go back up in recursion and move on to the next possible combination, using an approach called backtracking.

Using backtracking, maintain a curr array that keeps track of the current components of the sum. After adding a number to the curr, decrement target by that number, so that on the next level of recursion, that would be the new target. Whenever our target ends up decrementing to 0 (which is our base case, meaning that we've found a combination of numbers that perfectly sum up to the target).

Approach

Backtracking typically involves a helper function and passing around arrays by reference so that the same one is maintained across all levels of recursion.

Note that to avoid having duplicates, we have to mark the index of the element we added, so that the search on the next level of iteration begins from that index and skips over anything before. However, this only works if the array is sorted, so that skipping the numbers before (and therefore avoiding unneeded examination of numbers we know can't be part of the sum) won't cause any harm.

void combination(vector<vector<int>>& res, vector<int>& candidates, vector<int>& curr, int target, int begin) {
    if (target == 0) {
        res.push_back(curr);
        return;
    }

    for (int i = begin; i < candidates.size(); i++) {
        if (candidates[i] > target)
            break;
        curr.push_back(candidates[i]);
        combination(res, candidates, curr, target - candidates[i], i);
        curr.pop_back();
    }
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    sort(candidates.begin(), candidates.end());
    vector<vector<int>> res;
    vector<int> curr;
    combination(res, candidates, curr, target, 0);
    return res;
}