Vibe Engines
YouTube

Vibe Engines is free, interactive AI engineering & system design — runs in your browser. Pick a learning path

Algorithm · Backtracking

Cut the Dead Branches.

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

8624222021333031553230535
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.

CallPath so farRemainingTriedOutcome
1(empty)82, 3, 5explored
2262, 3, 5explored
32+242, 3, 5explored
42+2+222, 3, 5explored
52+2+2+20–record
62+2+313, 5dead end
72+333, 5explored
82+3+30–record
92+515dead end
10353, 5explored
113+323, 5dead end
123+50–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.

CaseTimeSpaceWhy
Backtracking, prune on overshootO(n^(T/m)) worst caseO(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 overshootsame bound, fewer iterationsO(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 prunesame bound, more callsO(T/m)Every overshoot is a call: 23 against 13 on the page’s example.
Count only, with DPO(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 answersat least the size of the outputO(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
  1. Track the remaining amount rather than a running sum — the base cases get simpler.
  2. remaining == 0: record a copy of the path. remaining < 0: dead end, return.
  3. Recurse with i, not i + 1. That single character is what allows reuse of the current candidate.
  4. Still starting the loop at start is what prevents permutations of the same multiset appearing twice.
  5. Copy the path when recording it. Appending the live list gives you N references to one array that ends up empty.
CPython · WebAssembly

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.

Finished this one? 0 / 99 Algorithms done
NextThe Standoff: N-Queens Next on the “Try, fail, undo” ladder · rung 3 of 4

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

More Algorithms