Math Fundamentals18 sections · 814 units
Open in Course

Combination Sum - Reuse Strategy

Same index or skip

The main insight: when you pick a number, you can pick it again. So when you recurse, you pass the same start index instead of incrementing it.

For example, if you pick 22 from [2,3,6,7][2, 3, 6, 7], your next call still starts at index 00 (where 22 is). This lets you pick 22 again. Once you decide to skip 22, you move to index 11 and try 33.

Base case: when your sum equals the target, add the current combination to results. If sum exceeds target, stop exploring that path.