Don't memorize combination sum — watch the dead branches get cut. Given numbers you can reuse, find every combination that adds to a target. Backtracking explores the choices, but the real move is pruning: the instant a pick would overshoot what remains, that whole branch is abandoned. Same push-recurse-pop skeleton as listing subsets — now with a goal and a bound that make an exponential search fast.
reuse candidates · remaining = target − sum · prune on overshoot · record at 0
CANDIDATES
The numbers you may pick — each reusable any number of times.
REMAINING
remaining = target − sum(path). Success is exactly 0; below 0 is impossible.
PRUNE
If a candidate exceeds remaining, adding it overshoots — cut the branch, do not recurse.
NO DUPLICATES
Only pick from the current index onward, so 2,3 is found but never 3,2.
combsum.sim — candidates [2, 3, 5], target 8
Ready
Pick candidates (reusable) to hit target 8. The path grows, remaining shrinks. When a candidate is bigger than remaining it turns red — pruned. Reach exactly 0 and the combination is recorded. Press Step.
bt(start, rem): if rem==0 record; for i≥start: if c[i]≤rem pick & recurse(i), else prune
8
Remaining
0
Combinations
A goal and a bound
Item one of this series listed every subset by walking a decision tree with no brakes — all two-to-the-n of them. Combination sum reuses that exact skeleton but bolts on two things: a goal (the running total must land on the target) and a bound (it must never pass the target). The bound is where pruning lives. You carry a remaining value, and before recursing into a candidate you check: is it larger than what remains? If so, taking it — or anything bigger — can only overshoot, so you skip it outright and never build that subtree. Whole swaths of the search space vanish. What is left is only the branches that still have a chance.
01
Track remaining
Start with remaining = target. Subtract each pick. When it hits exactly 0, the path is a valid combination — record a copy.
02
Branch, allowing reuse
Loop candidates from a start index; recurse with the same index so a number can be chosen again.
03
Prune on overshoot
If candidate > remaining, skip it. With sorted candidates, everything after it also overshoots — the whole tail is cut.
04
Pop and backtrack
After exploring a pick, pop it and move to the next candidate. Advancing the start index avoids duplicate orderings.
Combos found
3
Time
O(n^(T/m))
Space
O(T/m)
Pattern
Prune + BT
The worst-case bound looks scary — the tree can be as deep as target over the smallest candidate, branching over n choices — but pruning is what makes it practical. Every problem in this family lives or dies by how aggressively you cut: sort the candidates so overshoot ends a whole tail at once, drop below zero and stop, spot that no remaining candidate can reach the goal. The lesson generalizes: N-Queens prunes on attacked squares, Sudoku on illegal digits. Backtracking without pruning is brute force; backtracking with pruning is an algorithm.
Check yourself
1 · What makes combination sum fast compared to listing all subsets?
The bound (never exceed the target) lets you abandon a branch the instant a candidate is bigger than what remains, erasing huge parts of the search tree.
2 · Why does the recursive call keep the same index i?
Reuse is permitted, so recursing on i (not i+1) lets a number like 2 be picked again and again, e.g. 2+2+2+2.
3 · Why only pick candidates from the current index onward?
Choosing in non-decreasing index order generates each unordered combination exactly once, never a reshuffle of one already found.
Questions
Combination sum vs listing all subsets?
Same backtracking skeleton. Subsets enumerate all 2ⁿ possibilities blindly. Combination sum adds a target (keep only paths that sum to it) and a bound (prune anything that overshoots), and it allows reuse — so combinations can be longer than the candidate list.
What if each candidate can be used only once?
That is the classic follow-up (combination sum II). Recurse with i + 1 instead of i, and skip over equal candidates at the same depth so duplicate combinations are not produced.
Why is the complexity so hard to pin down?
It depends on the target and the smallest candidate: the tree can be as deep as target / min and branch over n candidates. Pruning cuts most of that in practice, so the real cost is far below the worst-case O(n^(T/min)).
Backtracking without pruning is brute force.
Carry the remaining amount, cut every branch that overshoots, record the ones that land on zero. That single bound is the whole difference.