Combination sum with a start index

47 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Coins of value 2, 3, 6 and 7, as many of each as you like. Which multisets of coins add up to 7? By hand: 2+2+3 and 7. Easy for a target of 7. Now imagine listing all ways to make 30 with those coins. You would soon write 2+2+3+... and later 3+2+2+..., the same bag of coins in a different order, and have to cross one out. Avoiding those duplicates by checking every new answer against the old ones is slow and error prone.

Build the structure, one piece at a time

Piece one: sort the coins: [2, 3, 6, 7]. Piece two: a path, the coins chosen so far, as a stack. Piece three: remaining, the target minus the path's sum.

Piece four, the rule that kills duplicates: a start index. When you are choosing the next coin, you may choose only coins at position start or later. If you chose the coin at position p, the next choice starts at p again, not p + 1, because reuse is allowed, but never earlier. That forces every path to be written in non-decreasing order, so 2+2+3 can appear but 3+2+2 cannot.

Piece five: pruning. Because the coins are sorted, once a coin is bigger than remaining, every later coin is too, so stop the loop.

Why it is correct

The invariant: the path is always sorted, because each new coin comes from the current start or later and start never moves backwards. Every multiset of coins has exactly one sorted spelling, so each answer is recorded exactly once. Nothing is lost: any valid multiset, written in sorted order, is one of the paths the loop builds, since at each step its next coin is at or after the position of the previous one. Pruning is safe because remaining only shrinks along a path, so a coin too big now is too big for every deeper step too.

Why it is fast

Without the start index, a combination of k coins would be generated up to k factorial times (every ordering of its coins). With it, each of the C combinations is built once, costing about its length to copy:

work ≈ k · C plus the dead branches that pruning cuts short

The dead branches are bounded by the number of sorted prefixes whose sum stays under the target, which for small targets is tiny.

How to recognise it in an interview

Cues: "all combinations that sum to", "choose k of n", "may reuse" or "each once", "no duplicate combinations". The first thing to say: "backtrack with a start index so every combination is built in sorted order once." Combination Sum is the example above with reuse, so the recursive start is p. Combination Sum II forbids reuse and has duplicate coins: recurse with p + 1 and, within a level, skip a coin equal to the previous coin. Combinations is the same loop with the sum replaced by a count of k picks.

02The idea in one line

Only choose from index start onward so each combination is made once.

Reach for it when: Combination sum I/II/III, combinations, palindrome partitioning.

Cost: O(k · C) time for C combinations.

03The walk-through, step by step

The video works one example: Combination Sum [2,3,6,7] target 7. These are its captions in order, so you can follow without the video or check a step you missed.

1. Reuse allowed, but only choose from start onward so each set is made once
2. Take 2 (start = 0): remaining 7 − 2 = 5
3. Take 2 (start = 0): remaining 5 − 2 = 3
4. Take 2 (start = 0): remaining 3 − 2 = 1
5. 2 > remaining 1: candidates are sorted, prune the rest
6. Take 3 (start = 1): remaining 3 − 3 = 0
7. remaining = 0: 2+2+3 is a valid combination
8. 6 > remaining 3: candidates are sorted, prune the rest
9. Take 3 (start = 1): remaining 5 − 3 = 2
10. 3 > remaining 2: candidates are sorted, prune the rest
11. 6 > remaining 5: candidates are sorted, prune the rest
12. Take 3 (start = 1): remaining 7 − 3 = 4
13. Take 3 (start = 1): remaining 4 − 3 = 1
14. 3 > remaining 1: candidates are sorted, prune the rest
15. 6 > remaining 4: candidates are sorted, prune the rest
16. Take 6 (start = 2): remaining 7 − 6 = 1
17. 6 > remaining 1: candidates are sorted, prune the rest
18. Take 7 (start = 3): remaining 7 − 7 = 0
19. remaining = 0: 7 is a valid combination
20. Found 2+2+3 and 7; 3+2+2 never appears because start only moves forward
21. Branching bounded by target / smallest candidate: exponential, but pruned

04Asked at Google

6 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Backtracking: Subsets (include / exclude), Permutations with a used set, Grid DFS with undo, Constraint placement with pruning, Generate valid sequences.