STEP 7 · RECURSION · CANONICAL ORDER + REUSE INDEX · MEDIUM

Combination Sum

WHAT IT SAYS

Given distinct positive candidates and a target, find every unique combination summing to the target. A candidate may be reused as many times as you like.

WHAT IT'S REALLY ASKING

"The duplicates in your output are not duplicate numbers — they are duplicate ORDERS: [2,3] and [3,2] are the same answer wearing different clothes. So forbid going backwards. If every pick must be at least as large as the one before it, how many ways can a given multiset be built?"

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Try every candidate at every step, then de-duplicate

O(number of orderings) time, plus a set proportional to the garbage

At each level of the recursion, loop over ALL candidates, subtract, recurse, and collect the paths that land exactly on the target. Sort each surviving path and hash it into a set so that the repeats collapse.

WHERE THE WORK IS WASTED — Two crimes, both specific. First, a combination of k numbers is discovered once for every ORDER those k numbers can be picked in — so you manufacture up to k! copies of every answer and then pay a sort and a hash on each one to throw them away. Second, the recursion keeps descending after the running sum has already blown past the target. Every candidate is positive, so that subtree is arithmetically dead the moment the overshoot happens — and yet you walk it.

KEY OBSERVATION — THE UNLOCKlink

Every multiset has exactly one non-decreasing arrangement.

The over-generation is entirely about order, so kill the order. Insist that the picks come out in non-decreasing sequence. Why is that safe? Because for any multiset of numbers there exists exactly one non-decreasing way to write it — existence, so no answer is lost; uniqueness, so no answer is produced twice. The set of non-decreasing sequences and the set of multisets are in bijection. Choosing a canonical form does not filter the duplicates out; it makes them unrepresentable. Mechanically that is one parameter: a start index that the recursion may never look to the left of. And note the exact place where the reuse rule lives. Reuse allowed means that after picking candidate j you recurse on j again, not j+1 — you may take another copy of the same number and still be non-decreasing. Change that single index to j+1 and you have the no-reuse variant. That one character is the whole difference between this problem and its siblings. The second half of the observation is the pruning. Candidates are strictly positive, so the running sum only ever climbs — a partial that has overshot the target can never come back down. Overshooting is permanent, which makes cutting the subtree sound rather than merely hopeful. And if you sort the candidates first, the overshoot at candidate j guarantees an overshoot at every candidate after j too, so you break out of the loop entirely and kill all the remaining siblings with one comparison.

Sort, carry a start index, break on overshoot

O(number of combinations * average length) — the tree contains only living branches

Sort the candidates. Recurse with (start, remaining). For j from start to the end: if candidate[j] exceeds remaining, break — every later candidate is bigger and equally hopeless. Otherwise push it, recurse with (j, remaining - candidate[j]) — the same j, because reuse is allowed — then pop. Record the path whenever remaining hits exactly zero.

WHAT YOU TRADED — The canonical ordering is free and deletes an entire data structure — but it leans hard on positivity. Allow zero or negative candidates and the running sum stops being monotone, so the overshoot prune becomes unsound, and unlimited reuse of a zero would make the answer set infinite. The transferable lesson: de-duplicate by construction, never by filtering. If you find yourself hashing answers to spot repeats, your recursion is generating something the problem never asked for.

WATCH THE IDEA RUN

CANDIDATES — the window only ever moves right

CALL STACK

stack empty — every branch explored

current path empty

found 0

dedupe set needed none

Let every branch pick from the whole array and you generate [2,2,3], [2,3,2] and [3,2,2] — the same multiset three times, and you then need a set of sorted tuples to dedupe them. But every multiset has exactly ONE non-decreasing arrangement. So if the recursion is only ever allowed to pick a candidate at index ≥ the one it just picked, each multiset can be produced along exactly one path. Duplicates become unreachable rather than filtered. That is the `start` index. It is not an optimisation — it is a canonical form, enforced by construction.

step 1 / 49

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Canonical Order Kills Duplicates

YOU'LL SEE IT AGAIN WHEN

The answer is a combination or multiset, and the naive recursion produces every permutation of each one.
All values are positive, so a partial sum is monotone — overshooting is permanent, which licenses a prune.
The only difference between 'reuse allowed' and 'reuse forbidden' is whether the recursive call passes j or j+1 — the index IS the rule.

SAME BLUEPRINT, DIFFERENT PROBLEM

Combination Sum IICombination Sum IIICoin Change IISubsets

The bar isn't "solved it once." It's "could rebuild it from the observation."