Backtracking
What the start index controls
One number in the recursive call decides whether items can repeat and whether orderings count separately.
Key idea
The index in the recursive call
In a loop-over-choices search, what you pass as the next start index decides the entire character of the problem. Three values, three meanings, and confusing them is the source of most wrong answers in this unit.
| Recursive call | Meaning | Result |
|---|---|---|
| explore(index + 1) | move past this item | each item used at most once, combinations |
| explore(index) | this item may be reused | unlimited repeats, combinations |
| explore(0) | every item available again | orderings counted separately, permutations |
The same function with only that one argument changed produces genuinely different answers.
Why it works
Why passing `start` at all prevents duplicates
Without the start index, the loop would run from 0 every time and produce [1, 3] and [3, 1] as separate results. For a combination problem those are the same answer.
Restricting each level to items at or after the previous index forces every result to come out in non-decreasing index order, and there is exactly one such ordering per combination. That is how the duplicates are prevented: not by checking for them afterward, but by making them unreachable.
This is worth stating as a general principle. Deduplicating results after the fact is always possible and always worse; controlling the branching so duplicates are never generated is both faster and easier to reason about.
Tip
The early skip is a real optimization
The continue when a part exceeds the remaining target cuts off a branch that cannot possibly succeed. Without it the search still terminates correctly, having wasted time descending into hopeless subtrees.
If the parts are sorted, that continue can become a break, since everything after it is even larger. Sorting first to enable a break is a common and worthwhile move, and it is the subject of the pruning lesson later in this unit.
Edge cases
What counts as a base case
Here the base case is reaching exactly zero remaining. Overshooting is prevented by the skip rather than detected at the top, which keeps the base case to a single condition.
The alternative is to allow overshoot and check for a negative remaining at the start of the function. Both work; the first explores fewer nodes. Say which you chose so the interviewer knows the pruning was deliberate.
Which index does this need?
You must list every way to make change for an amount using given coin values, where each coin may be used any number of times, and where [1, 3] and [3, 1] count as the same way. What should the recursive call pass?
Combination Sum
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.