Problem overview
The method combinationSum2 receives a vector<int> named candidates, which may contain repeated numbers, and an int target. It returns every distinct combination of candidates that adds up to target, as a vector<vector<int>>. Each candidate can be used at most once, so a number that appears twice in the input can appear up to twice in one combination.
Two combinations are the same when they hold the same numbers the same number of times, whichever copies they use. With [1,1,7] and a target of 8, the first 1 with the 7 and the second 1 with the 7 are one combination, [1,7], and it is listed once. Each combination is written in ascending order, and the combinations are in lexicographic order: the first position where two of them differ decides. If nothing adds up to the target, the result is an empty vector.
For candidates = [10,1,2,7,6,1,5] and target = 8 the result is [[1,1,6],[1,2,5],[1,7],[2,6]]. Sorted, the candidates are [1,1,2,5,6,7,10]. [1,2,5] comes before [1,7] because at the second position 2 is smaller than 7. For [2,3] and a target of 4 the result is []: 2 + 3 is 5, and the 2 can't be used twice.
Approach: sorted backtracking with two pruning rules
The search builds a combination one number at a time. A call receives start, the first index it may still use, remaining, the amount the combination still needs, and current, the combination so far. When remaining is 0, current adds up to the target and is saved. Otherwise a loop tries each index i from start on as the next number: add candidates[i], call again with i + 1 and remaining - candidates[i], then remove the number so the loop can try the next one.
Sorting the candidates first pays off three times:
- Equal numbers sit side by side, so a repeat is spotted by comparing a number with the one before it.
- Each combination comes out in ascending order, and the combinations come out in lexicographic order, as required.
- Once a candidate is bigger than
remaining, every later one is too, so the loop can stop withbreak.
The two rules that make this problem different from one where a number can be reused are these. The recursive call starts at i + 1, so each position is used at most once. And the loop skips candidates[i] when i > start and it equals candidates[i - 1]: inside one call every turn of the loop picks a different next number, and a second copy of a value already tried would rebuild the same combinations. A copy is still used when it is the first one the call tries, at i == start, and that is how [1,1,6] gets its second 1.
Step by step
- Sort
candidateswithsort(candidates.begin(), candidates.end()). - Create
result, avector<vector<int>>for the combinations found. - Create
current, an emptyvector<int>: the combination being built. - Start the search at index 0 with all of
targetstill needed. - Return
result. The helper added to that same vector. - Declare the helper.
backtrackreturnsvoidand takescandidates,start,remaining,currentandresult. The vectors are references, because the helper changescurrentandresultand the caller must see it. - Check for a finished combination. When
remaining == 0, the numbers incurrentadd up to exactlytarget. - Save it and return. Every candidate is at least 1, so adding another number would go past the target.
- Loop with
ifromstartto the end ofcandidates. Starting atstart, never at 0, keeps each combination in index order and builds no choice of indexes twice. - Skip repeats: if
i > startandcandidates[i] == candidates[i - 1],continue. - Stop at a number that is too big: if
candidates[i] > remaining,break. - Choose the number with
current.push_back(candidates[i]). - Recurse with
i + 1as the new start andremaining - candidates[i]as the amount still needed. - Undo with
current.pop_back(), so the loop can try the next candidate in its place.
The solution in C++
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
vector<vector<int>> result;
vector<int> current;
backtrack(candidates, 0, target, current, result);
return result;
}
void backtrack(vector<int>& candidates, int start, int remaining, vector<int>& current, vector<vector<int>>& result) {
if (remaining == 0) {
result.push_back(current);
return;
}
for (int i = start; i < candidates.size(); i++) {
if (i > start && candidates[i] == candidates[i - 1]) {
continue;
}
if (candidates[i] > remaining) {
break;
}
current.push_back(candidates[i]);
backtrack(candidates, i + 1, remaining - candidates[i], current, result);
current.pop_back();
}
}
};
The C++ details worth a closer look:
- One shared
current. It is passed by reference, so the whole search builds and unbuilds a single vector. Eachpush_backhas a matchingpop_back, andresult.push_back(current)saves a copy of the vector as it is at that moment. continueandbreak.continueabandons the current turn of the loop and moves to the nexti.breakleaves the loop altogether. The first is right for a repeated value, because larger numbers may still fit. The second is right for a number that is too big, because the sorted order means every later one is too big as well.candidatesis sorted in place. The parameter is a non-const reference, so the caller's vector comes back sorted.- Signed and unsigned.
candidates.size()is unsigned andiis anint. The comparison is safe for these sizes, and compilers may warn about the mix.
Complexity
Time: O(n · 2^n) in the worst case, for n candidates. There are at most 2^n ways to pick some of them, and copying a combination takes up to n steps. In practice the search is far smaller, because it only builds distinct combinations whose sum stays within target.
The pruning has a visible effect. For 100 candidates equal to 1 and a target of 30, the search makes 31 calls and finds the single combination of thirty 1s. For the numbers 1 to 20 and a target of 30, the search with break makes 1,916 calls and finds 263 combinations. Without the break it finds the same 263 combinations in 953,017 calls.
Space: O(n) besides the answer: current and the recursion are at most n deep.
Edge cases and common mistakes
- Comparing with
i > 0instead ofi > start. That also skips a repeat that is the first number a call tries. Example 1 then returns[[1,2,5],[1,7],[2,6]], without[1,1,6]. - No skip at all. Example 1 returns 6 combinations, with
[1,2,5]and[1,7]twice each. For[1,1,7]and a target of 8 it returns[[1,7],[1,7]]. - Forgetting to sort. The skip and the
breakboth depend on the order. Without sorting, example 1 returns[]. - Recursing with
iinstead ofi + 1. A number could then be used again and again, which this problem forbids. - Using a repeated value more than once. That is allowed as long as the input has the copies:
[2,5,2,1,2]with target 5 gives[[1,2,2],[5]], using two of the three 2s. - No solution.
[2,3]with target 4 gives[], and a single candidate that doesn't reach the target,[1]with target 2, also gives[]. - Equal candidates that complete the target.
[3,3,3]with target 6 gives only[[3,3]].
Testing
[10,1,2,7,6,1,5], target 8 gives[[1,1,6],[1,2,5],[1,7],[2,6]].[2,5,2,1,2], target 5 gives[[1,2,2],[5]].[2,3], target 4 gives[].[1,1,7], target 8 gives[[1,7]].[1], target 1 gives[[1]].[1,1,1,1], target 2 gives[[1,1]].
