Combination Sum
Reuse allowed: recurse on the same index until the remaining target goes negative.
The Search Tree, Step by Step
Problem
Given a list of distinct positive integers and a target value, return every unique combination whose values add up exactly to the target. A candidate may be selected more than once, and combinations may be returned in any order. Do not include duplicate combinations that differ only in ordering.
Examples
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Input: candidates = [2,4,5], target = 8
Output: [[2,2,2,2],[2,2,4],[4,4]]
The Goal
Find every combination of candidates that adds up to the target. A candidate can be used any number of times, and [2, 2, 3] and [3, 2, 2] count as one combination.
For [2,3,6,7] and target 7, the answer is [[2, 2, 3], [7]].
Reuse, but never reorder
2 can appear twice in one combination. But once a combination moves on to 3, it never goes back to 2, so each set is built in one order only.
Candidates only go forward.
Key Idea: Recurse From the Same Index
Sort the candidates. Each call knows what's left of the target and which candidate it may start from.
Choosing candidates[i] recurses with the same i, so that candidate can be chosen again, but nothing before it. When nothing is left, record the path. When a candidate is bigger than what's left, stop the loop: every candidate after it is bigger too.
Recurse with start = i, not i + 1.
2 can follow 2.
The Algorithm
def combination_sum(candidates, target):
candidates.sort()
result = []
path = []
def backtrack(start, remaining):
if remaining == 0:
result.append(path[:])
return
for i in range(start, len(candidates)):
if candidates[i] > remaining:
break
path.append(candidates[i])
backtrack(i, remaining - candidates[i])
path.pop()
backtrack(0, target)
return resultpath.pop() undoes each choice, so the next candidate starts from the same path.
Why does the recursive call pass i, not i + 1?
Walkthrough
Run it on [2,3,6,7] with target 7. Each node on the stage shows what's left, and each edge the candidate chosen.
Taking 2 three times leaves 1, and 2 is already too big for that, so the loop stops. Back at [2, 2], a 3 leaves exactly 0: record [2, 2, 3].
The branches that start with 3 and 6 run out of room. 7 alone hits 0: record [7]. Seven branches are cut off before they're ever called.
Checkpoint · predict the next step
Step 12 of 38 on the stage: Record [2, 2, 3]: combination 1.
path = [2, 2, 3] · result = [[2, 2, 3]] · remaining 0
Pitfalls
- Recurse with
i, noti + 1, or[2, 2, 3]can't be built. - Start the loop at
start, not 0, or[2, 2, 3]also comes back as[2, 3, 2]and[3, 2, 2]. breakis only safe on sorted candidates. Unsorted, usecontinue.- Append a copy,
path[:]. Appendingpathitself records a list that later pops back to empty. - A target smaller than every candidate gives
[].
If the loop started at 0 instead of start, what would go wrong on [2,3,6,7] and 7?
Complexity
The search tree is what costs. With target T and smallest candidate m, a path is at most T / m deep, and each call can branch once per candidate. So the number of calls grows exponentially with T / m, and pruning only trims it.
Apart from the answers, space is the path and the call stack, O(T / m).
An exponential search, pruned
- Calls in the search treeExponential in how deep paths go.dominantO(2^n)
- Copy each answerA path is at most target / m long.O(target)
- Path and call stackOne frame per choice on the path.O(target)
| n | 10 | 100 | 1,000 | 10,000 |
|---|---|---|---|---|
| O(2ⁿ) | 1K | > 10¹⁵ | > 10¹⁵ | > 10¹⁵ |
| O(n) | 10 | 100 | 1K | 10K |
Exponential, as any search that lists every answer can be. Pruning cuts branches early.
In short
Backtrack, subtracting a chosen candidate from the target. Since numbers can repeat, recurse with the same start index; move to the next index only when you decide to stop using the current candidate. Prune when the remainder drops below zero.
Common mistake
Advancing the start index after every pick, which forbids reusing a number the problem allows.