Problem overview
The method combinationSum(candidates, target) receives a list of distinct integers and a target. It returns every combination of candidates that adds up to the target. A candidate may be used any number of times, and two combinations count as the same when they use the same numbers the same number of times, in any order, so [2, 2, 3] and [3, 2, 2] are one combination.
Each combination is written 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 the target, the result is an empty list.
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]]: the input isn't sorted, but the output still is. For [2] and 1 the answer is [].
Approach: build combinations one number at a time
This is a search problem, and the standard tool is backtracking. Build a combination by repeating one move: choose a candidate, add it to the combination, and try to finish the rest with what is left of the target. Then undo the choice and try the next candidate.
Two ideas keep the search correct and tidy:
- Only move forward through the sorted candidates. After sorting, each call may only use candidates from index
ionward, whereiis the position of the last number chosen. The next number can be the same one (indexjagain) or a larger one, never a smaller one. So[2, 2, 3]is built, but[3, 2, 2]never is, and every combination appears exactly once, already in ascending order. The combinations also come out in lexicographic order, because the loop tries smaller candidates first. - Stop early. The candidates are sorted, so once one is bigger than what remains, every later one is too. The loop can
breakthere.
The search is exponential. With n candidates, a target t and smallest candidate m, a combination has at most t / m numbers, each one of n candidates, so the time is O(n^(t/m)) in the worst case. Here the target is at most 40 and every candidate is at least 2, which keeps the search small.
Step by step
The outer method
- Sort
candidatesin place withsort(). This gives the ascending order inside each combination, the lexicographic order of the answer, and the early stop. - Create
result, an empty list that will hold the finished combinations, each of them a list. - Start the search with
self.backtrack(candidates, target, 0, [], result): all of the target is still needed, any candidate from index 0 may be used, and the combination so far is empty. - Return
result.backtrackfills this same list.
The helper backtrack
- Declare it with
candidates,remaining(how much is still needed),i(the first index it may use),current(the combination so far) andresult. - If
remainingis 0, the numbers incurrentadd up to exactly the target. Appendcurrent.copy()toresultand return. The copy is essential:currentkeeps changing as the search goes on, so the result needs a snapshot. Returning here is also right because every candidate is at least 2, so adding more would overshoot. - Loop
joverrange(i, len(candidates)). These are the numbers the combination may take next. - Break if
candidates[j]is bigger thanremaining. Later candidates are even bigger. - Choose: append
candidates[j]tocurrent. - Recurse with
remaining - candidates[j]andjas the start index. Passingjand notj + 1is what allows the same number to be used again. - Undo:
current.pop()removes the number just chosen, socurrentis what it was before this turn of the loop.
The solution in Python
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
result = []
self.backtrack(candidates, target, 0, [], result)
return result
def backtrack(self, candidates, remaining, i, current, result):
if remaining == 0:
result.append(current.copy())
return
for j in range(i, len(candidates)):
if candidates[j] > remaining:
break
current.append(candidates[j])
self.backtrack(candidates, remaining - candidates[j], j, current, result)
current.pop()
Python details to know:
sort()sorts in place and returnsNone. That is why the code calls it on its own line and keeps usingcandidates, rather than writingcandidates = candidates.sort(), which would set it toNone. It also reorders the list the caller passed in.- Lists are shared, not copied, when passed around. Every call of
backtrackworks on the samecurrentand the sameresult. Appendingcurrentitself, without.copy(), would store a reference to the one list that is later emptied. In this problem every stored entry would end up as[]. range(i, len(candidates))is empty wheniequals the length, so the loop simply does nothing in that case.
Complexity
The time is exponential, O(n^(t/m)) in the worst case, as explained above, plus the cost of copying each combination into the result. The extra space, besides the answer, is O(t / m): the combination being built holds at most t / m numbers, and the recursion is at most that many calls deep.
Edge cases and common mistakes
- No combination.
[2]with target 1 returns[], since the loop breaks on the first candidate and nothing is ever added. - Repeating a number.
[3]with target 9 returns[[3, 3, 3]]: one candidate can fill the whole sum. - Starting the loop at 0 every time. Each call would try all candidates, so the same combination would appear in several orders, such as
[2, 2, 3],[2, 3, 2]and[3, 2, 2]. - Passing
j + 1to the recursive call. That forbids reusing a number, so[2, 3]with target 6 would lose[2, 2, 2]and[3, 3]. - Forgetting to undo. Without the
pop(),currentkeeps growing and every later combination is wrong. - Unsorted input.
[7, 3, 2]with target 7 returns[[2, 2, 3], [7]], in ascending order, because of the sort at the start.
Testing
| candidates | target | result |
|---|---|---|
[2, 3, 6, 7] | 7 | [[2, 2, 3], [7]] |
[5, 2, 3] | 8 | [[2, 2, 2, 2], [2, 3, 3], [3, 5]] |
[2] | 1 | [] |
[3] | 9 | [[3, 3, 3]] |
[2, 3] | 6 | [[2, 2, 2], [3, 3]] |
[7, 3, 2] | 7 | [[2, 2, 3], [7]] |
