Combination Sum
Find every combination summing to a target when numbers may be reused, and learn pruning — the move that makes backtracking fast
Problem Statement
Given an array of distinct integers candidates and a target, return all unique combinations that sum to target.
The same number may be chosen any number of times. Two combinations are different only if the counts of chosen numbers differ.
Input: candidates = [2, 3, 6, 7], target = 7
Output: [[2, 2, 3], [7]]
Input: candidates = [2, 3, 5], target = 8
Output: [[2, 2, 2, 2], [2, 3, 3], [3, 5]]Intuition
This combines the two ideas from the previous pages, then adds a third.
| Feature | Where it comes from |
|---|---|
Combinations, not orderings — [2,2,3] and [2,3,2] are the same | Subsets: use a start index |
| Numbers may repeat | New: recurse with i rather than i + 1 |
| Only paths hitting the target count | New: the base case tests a running sum |
The key insight
Reuse costs exactly one character. In Subsets you recurse with i + 1 to move past the chosen element. Here you recurse with i — staying put, so the same number can be chosen again.
Still no going backwards, so [3, 2] can never be produced after [2, 3]. Duplicates are avoided and reuse is allowed at the same time.
Why the search still ends
If a number can be reused forever, why does the recursion terminate?
Because the target shrinks with every choice. Every candidate is positive, so remaining strictly decreases and must eventually hit 0 or go negative. Both are stopping conditions.
This breaks if zero or negatives are allowed
A candidate of 0 would let the search take it forever without changing remaining — an infinite loop.
The problem guarantees positive candidates. If it did not, this approach would need rethinking entirely.
Pruning: the move that matters
Sort the candidates first. Then, inside the loop, when candidates[i] > remaining you can stop — not just skip.
candidates sorted = [2, 3, 6, 7], remaining = 1
i=0: 2 > 1 → too big.
And 3, 6, 7 are all bigger still.
So BREAK, not continue.Without sorting you would have to continue and test every remaining candidate. With sorting, one failed test rules out the entire rest of the loop.
continue vs break
continue skips one candidate. break abandons every candidate after it too.
Sorting is what earns you the right to break, and on deep searches that turns a slow solution into a fast one. It does not change the answer — only how much work is wasted getting there.
Approach
Sort the candidates
Only to enable pruning. The answer is identical without it, just slower.
Record when remaining hits exactly zero
The path sums to the target. Record a copy and return.
Loop from start, and break when a candidate is too big
Because the list is sorted, the first candidate exceeding remaining means every later one does too.
Choose, explore with i (not i + 1), undo
Passing i keeps the current number available for the next level, which is what allows [2, 2, 2].
Watch it run
Solution
def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
"""Every combination summing to target, with unlimited reuse."""
# Sorting is only for pruning — the answer is the same without it.
candidates.sort()
results: list[list[int]] = []
path: list[int] = []
def backtrack(start: int, remaining: int) -> None:
if remaining == 0:
results.append(path[:]) # copy, not the live array
return
for i in range(start, len(candidates)):
# Sorted, so if this one is too big every later one is too.
if candidates[i] > remaining:
break
path.append(candidates[i]) # choose
backtrack(i, remaining - candidates[i]) # explore — i, not i + 1
path.pop() # undo
backtrack(0, target)
return resultsThree one-character mistakes
| Written | Effect |
|---|---|
backtrack(i + 1, ...) | No reuse — becomes a different problem (each number used at most once) |
backtrack(0, ...) | No start floor — produces [2,3] and [3,2] as separate answers |
continue instead of break | Still correct, just slower — the pruning is wasted |
The first two change the answer. Only the third is merely a performance issue.
Complexity Analysis
Time Complexity
O(n^(T/m))
Space Complexity
O(T/m)
Where T is the target, m is the smallest candidate, and n is the number of candidates.
- Time — the deepest a path can go is
T/m, since each step subtracts at leastm. At each level there are up tonbranches, givingn^(T/m)in the worst case. Pruning cuts this dramatically in practice but does not change the bound. - Space — excluding the output: the recursion stack and
path, both bounded by the maximum depthT/m.
Why the bound looks so unusual
Most complexities are written in terms of the input size. Here the cost depends on the target value and on how small the candidates are.
With candidates = [1] and target = 100, the path is 100 deep. With candidates = [50] and the same target, it is 2 deep. Same input size, wildly different work — which is why T/m appears rather than n.
Edge Cases
Related Problems
- Subsets — the start index, without reuse
- Permutations — where order matters and no floor applies
- Coin Change — the same shape, but asking for the fewest coins rather than every combination, which makes it DP
- Backtracking — the template and the pruning idea