Problem overview
The method combinationSum(candidates, target) receives an array of distinct integers and a target. It returns every combination of candidates that adds up to target, where each candidate can be used any number of times. Order inside a combination doesn't matter, so [2, 2, 3] and [3, 2, 2] count as one. Each combination is written in ascending order, and the combinations are returned in lexicographic order. If none exists, the result is an empty array.
For candidates = [2, 3, 6, 7] and target = 7 the answer is [[2, 2, 3], [7]]. For [5, 2, 3] and 8 it is [[2, 2, 2, 2], [2, 3, 3], [3, 5]], even though the input isn't sorted. For [2] and 1 it is [].
Approach: build combinations one number at a time
The search builds a combination step by step. At each step it picks a candidate, subtracts it from what is still needed, and continues. When nothing is needed any more, the combination is complete. When the next candidate is bigger than what remains, it can't be used.
Two choices keep the answer free of duplicates and in the required order:
- Sort the candidates first. Combinations then come out in ascending order, and the first position where two combinations differ decides their order in the result, exactly the lexicographic order the task asks for.
- Only move forward in the list. A call may use candidates from index
ionward, never earlier ones. The same candidate can repeat, because the next call starts at the same index, but[3, 2, 2]can never be built after a 3, since the 2s are behind it.
Because the list is sorted, once one candidate is too big, every later one is too, so the loop can stop with break instead of skipping them one by one.
After exploring a choice, the search removes the number again and tries the next one in its place. That undo is what makes it backtracking.
Step by step
combinationSum
- Sort
candidatesin place with the comparison(a, b) => a - b. Without a comparison,sortcompares numbers as text. - Create the empty array
result, which will hold the combinations. - Start the search with
this.backtrack(candidates, target, 0, [], result): all oftargetis still needed, any candidate from index 0 may be used, and nothing is chosen yet. - Return
result, whichbacktrackhas filled.
backtrack
- If
remainingis 0, the numbers incurrentadd up to the target. Push a copy ofcurrentontoresultand return. Every candidate is at least 2, so adding more would overshoot anyway. - Loop
jfromito the end ofcandidates. - If
candidates[j]is bigger thanremaining,break. - Push
candidates[j]ontocurrent. - Call
backtrackwithremaining - candidates[j]andjas the first index. Passingjrather thanj + 1is what allows a number to be reused. - Pop the last number off
current, so the loop can try the next candidate from the same starting point.
The solution in JavaScript
class Solution {
combinationSum(candidates, target) {
candidates.sort((a, b) => a - b);
const result = [];
this.backtrack(candidates, target, 0, [], result);
return result;
}
backtrack(candidates, remaining, i, current, result) {
if (remaining === 0) {
result.push([...current]);
return;
}
for (let j = i; j < candidates.length; j++) {
if (candidates[j] > remaining) {
break;
}
current.push(candidates[j]);
this.backtrack(candidates, remaining - candidates[j], j, current, result);
current.pop();
}
}
}
The JavaScript details worth knowing:
- The comparison function.
[10, 9, 1, 2].sort()gives[1, 10, 2, 9], because the default sort compares text.(a, b) => a - breturns a negative number whenashould come first, so the numbers end up in numeric order.sortchanges the array it is called on, so the caller'scandidatescomes back sorted. - Copying with
[...current].currentis a single array that the search keeps changing. Pushingcurrentitself would store the same array many times, and after the search it would be empty. The spread syntax builds a new array with the same numbers, a snapshot of this moment. pushandpop. Both change an array at its end in constant time, which is why the array is shared between calls instead of copied.- Shared arrays.
resultandcurrentare passed by reference, so every call works on the same two arrays. This is whybacktrackneeds no return value.
Complexity
Time: exponential, O(n^(t/m)) in the worst case, where n is the number of candidates, t the target and m the smallest candidate. A combination has at most t / m numbers, and each one is one of n candidates. The sorted order and the break prune much of this in practice. Copying each finished combination adds a factor of its length.
Space: O(t / m) besides the answer: the combination being built and one call per number in it.
Edge cases and common mistakes
- No combination. For
[2]and1the first candidate is already bigger than what remains, so the loop breaks and the result stays[]. - A candidate equal to the target.
[7]with target 7 returns[[7]]. - Reusing a number.
[2, 3]with target 6 returns[[2, 2, 2], [3, 3]]. - Starting every loop at 0. The search would then build
[2, 2, 3],[2, 3, 2]and[3, 2, 2]as different combinations. - Passing
j + 1. Each number would be used at most once, which solves a different problem. - Pushing
currentwithout copying. The result holds references to the same array, which is empty once the search finishes. - Forgetting
pop(). Numbers pile up incurrentand later combinations contain leftovers. - Sorting without a comparison. Candidates such as
[10, 2]sort as[10, 2], which breaks both the order and thebreaktest. With the comparison,[10, 2]and target 12 returns[[2, 2, 2, 2, 2, 2], [2, 10]].
Testing
[2, 3, 6, 7]with target 7 gives[[2, 2, 3], [7]].[5, 2, 3]with target 8 gives[[2, 2, 2, 2], [2, 3, 3], [3, 5]].[2]with target 1 gives[].[2, 3]with target 6 gives[[2, 2, 2], [3, 3]].
