Combination Sum

Backtracking · Choose with a remaining target · Stretch · about 30 min

Why it matters

It shows how one backtracking template adapts to a new rule.

How it connects

The choice/explore/unchoose template stays the same; now the remaining target decides when to stop.

Try first

Which two base cases happen when the remaining target reaches 0 or drops below 0?

Interview cue

The remaining target is the recursive state, and start index keeps combinations ordered.