Given distinct positive candidates and a target, return all unique combinations whose values sum to the target. A candidate may be used any number of times.
Before you code
Reusing a candidate means the recursive call starts at the same index, not the next one. Without a rule like that, the same combination appears in several orders.
Hints
- Recurse with
(start, remaining). Whenremaining == 0, record the path. - Loop
ifromstart; choosecandidates[i]and recurse with(i, remaining - candidates[i]). - Sort the candidates first. Then, once a candidate exceeds
remaining, every later one does too, sobreakout of the loop.
Production & complexity notes
When solving Combination sum on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Backtracking basics to reinforce the underlying pattern.
What it practices
The choose, explore, unchoose pattern and pruning, from Backtracking basics.