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.
The picture: the whole search tree
Candidates [2, 3, 5], target 8. Each box is the amount still to make after the pick written at its upper left, so the root is 8 and a path from the root is a combination. Boxes at 0 (highlighted) are the three answers: 2+2+2+2, 2+3+3 and 3+5. Red boxes are dead ends: something is still owed but no candidate at or after the current index fits. The picks never go back to a smaller candidate than the one before, which is why 3+2+3 is not in the tree.
Worked example, step by step
Run combination_sum([2, 3, 5], 8) and log every call as bt(start, remaining) in the order the recursion makes them. The table shows the first 12 of the 13. In the Tried column a struck-through candidate was larger than remaining and was cut before it was recursed into.
Call
Path so far
Remaining
Tried
Outcome
1
(empty)
8
2, 3, 5
explored
2
2
6
2, 3, 5
explored
3
2+2
4
2, 3, 5
explored
4
2+2+2
2
2, 3, 5
explored
5
2+2+2+2
0
–
record
6
2+2+3
1
3, 5
dead end
7
2+3
3
3, 5
explored
8
2+3+3
0
–
record
9
2+5
1
5
dead end
10
3
5
3, 5
explored
11
3+3
2
3, 5
dead end
12
3+5
0
–
record
The recursion goes straight down the 2s first (calls 1 to 5), reaches 0 on call 5 and records [2, 2, 2, 2], then pops one 2 and tries 3 in its place. Calls 5, 8, 12 are the three records. The search made 13 calls in total. Check the bound at the top of each call instead of before recursing and the same answers cost 23 calls, because every overshoot becomes a call of its own that does nothing but return. The gap widens with the target: target 8 takes 13 calls with the early cut against 23 without it, for the same 3 combinations; target 20 takes 91 calls with the early cut against 131 without it, for the same 11 combinations; target 40 takes 521 calls with the early cut against 655 without it, for the same 34 combinations.
Complexity and trade-offs
Let n be the number of candidates, T the target and m the smallest candidate.
Case
Time
Space
Why
Backtracking, prune on overshoot
O(n^(T/m)) worst case
O(T/m)
The deepest path is T/m picks of the smallest number. Pruning shrinks the tree but not the worst-case bound; output size matters too.
Sorted, break at first overshoot
same bound, fewer iterations
O(T/m)
Once one candidate is too big every later one is too, so the loop ends instead of testing each.
Check at entry, no early prune
same bound, more calls
O(T/m)
Every overshoot is a call: 23 against 13 on the page’s example.
Count only, with DP
O(n·T)
O(T)
One array of ways per amount. It tells you there are 34 combinations for target 40 but cannot list them.
Listing all answers
at least the size of the output
O(output)
No method can beat writing down every answer, so a problem with many answers is slow whatever you do.
The trade-off is listing against counting. If you only need to know how many ways, or whether one exists, dynamic programming over amounts is polynomial in T; backtracking is the tool when the answers themselves are the output. Backtracking’s memory is small, just the current path, which is why it stays usable on cases where the answer list is long.
Common mistakes
Recursing with i + 1
That is the “each number once” version. With reuse forgotten, [2, 3, 5] and target 8 returns only [3, 5], and the combinations that repeat a number vanish.
Starting the loop at 0 instead of at start
Every order of the same numbers counts as a new answer. The same input returns 6 lists rather than 3, among them [2, 3, 3], [3, 2, 3] and [3, 3, 2].
Recording the live path
Appending path itself rather than a copy stores one list 3 times, and by the time the recursion unwinds that list is empty: the result is [[],[],[]]. Record path[:] or list(path).
Using break on unsorted candidates
Breaking at the first oversized candidate is only valid if the rest are bigger. With [5, 2, 3] it returns [2, 2, 2, 2], [2, 3, 3]; sorted input finds 3.
Allowing 0 or negative candidates
With a candidate of 0, remaining never shrinks and the recursion never ends (Python raises RecursionError), so validate that candidates are positive. With negatives the overshoot bound stops being a bound.
Where this shows up
Making change, all ways
Listing every way to pay an amount from a set of coin or note values is exactly this search. The counting version of the same question is the coin-change DP.
Exact-budget selection
Choosing items whose prices add up to a budget, or cutting a stock length into pieces of allowed sizes with no waste, are the same shape: repeat-allowed picks that must land on a total.
Constraint solvers and branch-and-bound
Cutting a branch the moment a bound is violated is the core of backtracking solvers for N-Queens, Sudoku and many scheduling problems; combination sum is the cleanest place to see it.
Subset sum and its relatives
Without reuse the problem becomes subset sum; with a limited count per item it becomes bounded knapsack-style enumeration. The skeleton stays the same, only the index you recurse on changes.
SOLVE IT YOURSELF
Solve it: every way to hit the target
Backtracking with one twist — you may reuse a number as many times as you like, which changes exactly one character of the recursion. Python or TypeScript, running for real in your browser.
YOUR TASK
Implement combination_sum(candidates, target): return every combination of the (distinct, positive) candidates that sums to target. Numbers may be reused unlimited times, and [2,2,3] and [2,3,2] count as the same combination — return each only once.
HINTS — 5 IDEAS
Track the remaining amount rather than a running sum — the base cases get simpler.
remaining == 0: record a copy of the path. remaining < 0: dead end, return.
Recurse with i, noti + 1. That single character is what allows reuse of the current candidate.
Still starting the loop at start is what prevents permutations of the same multiset appearing twice.
Copy the path when recording it. Appending the live list gives you N references to one array that ends up empty.
CPython · WebAssembly✓ Solved
1
1
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.