Problem overview
The method combinationSum(candidates, target) receives an array of distinct integers and a target. It returns every combination of the candidates that adds up to target. A candidate may be used any number of times. Two combinations are the same when they use the same numbers the same number of times, in any order, so [2, 2, 3] and [3, 2, 2] count once. Each combination is written in ascending order, and the combinations are returned in lexicographic order: the first position where two of them differ decides which comes first. If nothing adds up to the target, the result is an empty array.
For candidates = [2,3,6,7] and target = 7 the answer is [[2,2,3],[7]]: 2 + 2 + 3 = 7, and 7 alone is 7. For candidates = [5,2,3] and target = 8 the answer is [[2,2,2,2],[2,3,3],[3,5]], even though the candidates aren't sorted. For candidates = [2] and target = 1 the answer is [].
Approach: build combinations one number at a time
There is no formula for this; the task is to list every answer, so the solution searches. It builds a combination one number at a time. At each point it knows how much is still needed (remaining), and it tries each candidate as the next number. After choosing one, it calls itself with the smaller remainder. When the remainder reaches exactly 0, the numbers chosen add up to the target, and the combination is saved. Then the last choice is undone and the next candidate is tried: that is backtracking.
Two ideas keep the search tidy.
- Never go backwards in the list. A combination is built from candidates in sorted order, so after choosing the candidate at index
j, the next number comes from indexjor later. Indexjitself is allowed, which is how a number can repeat. Starting the loop at the last chosen index means[2, 2, 3]is found and[3, 2, 2]never is, so each combination appears once and already in ascending order. - Stop early. With the candidates sorted, once one candidate is bigger than
remaining, all the later ones are too, so the loop can stop.
Sorting also gives the output order. Trying candidates from the smallest up produces the combinations in lexicographic order without any extra sorting of the result.
Step by step
combinationSum
- Sort the candidates in place with
candidates.sort((a, b) => a - b). Without the comparison function,sortcompares numbers as text. - Create
result, an emptynumber[][], where finished combinations are collected. - Start the search with
this.backtrack(candidates, target, 0, [], result): all of the target is still needed, index 0 is the first usable candidate, and nothing is chosen yet. - Return
result, which the helper has filled.
backtrack
- Declare the helper with the parameters
candidates,remaining,i(the first index it may use),current(the combination so far) andresult. It returnsvoid: its output goes intoresult. - Base case. If
remaining === 0, the numbers incurrentadd up to the target. - Save a copy. Push
[...current]ontoresultand return. A copy is needed becausecurrentkeeps changing as the search goes on. Every candidate is at least 2, so adding more could only overshoot, and stopping here is right. - Loop over the choices with
jfromito the end of the candidates. - Break when too big. If
candidates[j] > remaining, leave the loop. - Choose
candidates[j]by pushing it ontocurrent. - Recurse with
remaining - candidates[j]andjas the first usable index. Passingj, notj + 1, allows the same number again. - Undo the choice with
current.pop(), so the loop can try the next candidate from the same state.
The solution in TypeScript
class Solution {
combinationSum(candidates: number[], target: number): number[][] {
candidates.sort((a, b) => a - b);
const result: number[][] = [];
this.backtrack(candidates, target, 0, [], result);
return result;
}
backtrack(candidates: number[], remaining: number, i: number, current: number[], result: number[][]): void {
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();
}
}
}
Details worth knowing:
- The comparison function.
[10, 9, 2].sort()gives[10, 2, 9], because the default order compares the numbers as strings.[10, 9, 2].sort((a, b) => a - b)gives[2, 9, 10]. Note thatsortchanges the array it is called on, so the caller'scandidatesends up sorted. - Why the copy matters. Pushing
currentitself would put the same array object intoresultmany times. After the search finished and every number was popped, each entry would be the same empty array.[...current]copies the numbers into a new array at the moment the combination is complete. - Everything is shared.
currentandresultare arrays, which JavaScript passes by reference. All the calls work on the same two arrays, which is why the helper doesn't need to return anything and why the undo step is needed. - Types are erased.
number[][]andvoidhelp the compiler and disappear in the generated JavaScript.
Complexity
Time: exponential. With n candidates, a target t and a smallest candidate m, a combination has at most t / m numbers, and each of them is one of n candidates, so the worst case is O(n^(t/m)). The sorted early exit cuts many branches in practice, and copying each answer costs time proportional to its length.
Space: O(t / m) besides the answer itself: the combination being built and one call for each number in it.
Edge cases and common mistakes
- No combination.
[2]with target 1 gives[], and[3, 5]with target 7 also gives[]. The loop breaks or ends and nothing reachesremaining === 0. - Repeated use.
[2]with target 4 gives[[2,2]]: the recursion passesj, so 2 can be chosen twice. - Starting the inner loop at 0. That would find the same combination in every order, such as
[2,2,3],[2,3,2]and[3,2,2], so the result would be full of duplicates. - Using
j + 1in the recursive call. That forbids repeats, so[2,2,3]would never be found. - Forgetting
pop(). The combination keeps growing with numbers from earlier branches. - Forgetting to sort. Without sorting, the early
breakwould skip candidates that fit, and the output would not be in ascending, lexicographic order. - Sorting without a comparison. Candidates such as
10and2would be ordered as text, putting 10 first.
Testing
candidates = [2,3,6,7],target = 7gives[[2,2,3],[7]].candidates = [5,2,3],target = 8gives[[2,2,2,2],[2,3,3],[3,5]].candidates = [2],target = 1gives[].candidates = [2],target = 4gives[[2,2]].candidates = [3,5],target = 7gives[].candidates = [10,2,3],target = 12gives[[2,2,2,2,2,2],[2,2,2,3,3],[2,10],[3,3,3,3]].
