Problem overview
combinationSum2(candidates, target) receives an array of integers that may repeat and a target. It returns every distinct combination of candidates that adds up to target. Each candidate may be used at most once, so a value that appears twice in candidates 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.
The numbers of each combination are in ascending order, and the combinations are returned in lexicographic order: compare number by number, and the first difference decides. If nothing adds up to target, the result is an empty array.
For candidates = [10,1,2,7,6,1,5] and target = 8 the answer is [[1,1,6],[1,2,5],[1,7],[2,6]]. The combination [1,7] can be built with either 1, but it is listed once. For [2,3] and target 4 the answer is []: the 2 can't be used twice.
Approach: sorted backtracking
Sort the candidates first. That gives three things at once: equal values sit side by side, the numbers of each combination come out in ascending order, and once a candidate is too big, every later one is too big as well.
A call of the search receives start, the first index it may still use, remaining, how much the combination still needs, and current, the combination built so far. When remaining is 0, current adds up to the target and a copy is saved. Otherwise a loop tries each index i from start on as the next number: it adds candidates[i], recurses with i + 1 and remaining - candidates[i], then removes the number again.
Two details handle the rules of this problem:
- The recursive call starts at
i + 1, so a candidate can't be picked twice. (If a variant allowed unlimited reuse, the call would passi.) - The loop skips
candidates[i]wheni > startand it equalscandidates[i - 1]. In one call, each turn of the loop picks a different next number, and a second copy of the same value would rebuild combinations that the first copy already produced. Ati = startthe copy is taken, because it is the first one this call tries. That is how[1,1,6]gets its second 1.
The brute-force idea is to try every subset of the candidates and keep those with the right sum, which is far more work than needed. Here the search never builds a combination that goes over the target.
Step by step
- Sort
candidatesin place with the comparison(a, b) => a - b. Without a comparison,sortcompares numbers as text. - Create
result, an empty array of combinations. - Start the search:
this.backtrack(candidates, 0, target, [], result). Every index may be used and all of the target is still needed. - Return
result. - Declare the helper
backtrack(candidates, start, remaining, current, result)in the class. - Stop at a full combination: if
remaining === 0... - ...save a copy with
[...current]andreturn. Every candidate is at least 1, so adding anything more would pass the target. - Loop
ifromstartwhilei < candidates.length. Starting atstart, never at 0, means a combination takes its numbers in index order, and no choice of indexes is built twice. - Skip repeats: if
i > startandcandidates[i] === candidates[i - 1], usecontinue. - Stop at a number that is too big: if
candidates[i] > remaining, usebreak. The array is sorted, so every later candidate is bigger still. - Choose
candidates[i]by pushing it ontocurrent. - Recurse with
i + 1andremaining - candidates[i]. - Undo with
current.pop()so the loop can try the next candidate.
The solution in JavaScript
class Solution {
combinationSum2(candidates, target) {
candidates.sort((a, b) => a - b);
const result = [];
this.backtrack(candidates, 0, target, [], result);
return result;
}
backtrack(candidates, start, remaining, current, result) {
if (remaining === 0) {
result.push([...current]);
return;
}
for (let i = start; i < candidates.length; i++) {
if (i > start && candidates[i] === candidates[i - 1]) {
continue;
}
if (candidates[i] > remaining) {
break;
}
current.push(candidates[i]);
this.backtrack(candidates, i + 1, remaining - candidates[i], current, result);
current.pop();
}
}
}
JavaScript details to watch:
- The comparator is required.
[10, 2].sort()compares"10"and"2"as text and puts 10 first.(a, b) => a - bsorts numerically. Note thatsortreorders the caller's array. - Copy before saving.
currentis one array reused by the whole search. Pushingcurrentitself would leaveresultfull of references to that array, which ends up empty.[...current]saves a snapshot. continueagainstbreak.continueskips one value and goes on to the nexti.breakleaves the whole loop, which is right only because the array is sorted.
Trace on [10,1,2,7,6,1,5], target 8
After sorting, the candidates are [1,1,2,5,6,7,10]. Printing the arguments at the start of each call gives:
start=0 remaining=8 current=[]
start=1 remaining=7 current=[1]
start=2 remaining=6 current=[1,1]
start=3 remaining=4 current=[1,1,2]
start=4 remaining=1 current=[1,1,5]
start=5 remaining=0 current=[1,1,6]
start=3 remaining=5 current=[1,2]
start=4 remaining=0 current=[1,2,5]
start=4 remaining=2 current=[1,5]
start=5 remaining=1 current=[1,6]
start=6 remaining=0 current=[1,7]
start=3 remaining=6 current=[2]
start=4 remaining=1 current=[2,5]
start=5 remaining=0 current=[2,6]
start=4 remaining=3 current=[5]
start=5 remaining=2 current=[6]
start=6 remaining=1 current=[7]
The calls with remaining=0 are the four answers, in the required order. The 10 is never chosen: it is bigger than every remaining the loop meets, so break stops before it. At the top level, the second 1 is skipped because i > start and it equals the one before, so [1,7] is found only once.
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 it is much smaller, because the search only builds distinct combinations whose sum is at most the target.
Extra space: O(n), besides the answer: the combination being built and one call per number in it.
Edge cases and common mistakes
- No duplicate check. For
[10,1,2,7,6,1,5]and target 8, a version without it returns[[1,1,6],[1,2,5],[1,7],[1,2,5],[1,7],[2,6]], with[1,2,5]and[1,7]twice. - Skipping with
i > 0instead ofi > start. The second 1 can then never follow the first, so[1,1,6]disappears and the result is[[1,2,5],[1,7],[2,6]]. - Recursing with
iinstead ofi + 1. This lets a candidate be used again: for[2,3]and target 4 it returns[[2,2]]instead of[]. - No combination.
[2,3]with target 4 gives[], and so does[10,20]with target 5. - Many copies.
[1,1,1,1]with target 2 gives[[1,1]]once, although there are six ways to choose two of the four 1s. - Forgetting the sort. Equal values might not be adjacent, so the skip test fails, and the
breakwould cut off candidates that still fit.
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,1,1], target 2 gives[[1,1]].[1], target 1 gives[[1]].[3,1,3,5,1,1], target 8 gives[[1,1,1,5],[1,1,3,3],[3,5]].
