Combination Sum
Given a set of distinct positive integers and a target, return all unique combinations of those numbers that sum to the target. Each number may be used unlimited times; two combinations are the same if they use the same multiset.
- 1 ≤ candidates.length ≤ 30
- 2 ≤ candidates[i] ≤ 40, distinct
- 1 ≤ target ≤ 40
- Return all combinations — enumerate
- Unlimited reuse, so recursion may stay at the same index
- Avoid duplicates by never going back to an earlier candidate
Enumerating every arrangement is exponential, so tiny bounds plus "all" or "any valid" wording mean search the decision tree: choose, recurse, un-choose. Pruning invalid partial states early (a queen already attacked, a sum already exceeded) is what makes it practical.
Recurse with a start index, the remaining target and the current combination. For each candidate from start onward, if it does not exceed the remaining target, add it, recurse with the same index (allowing reuse) and a reduced target, then remove it. Record the combination when the remaining target hits zero. Never revisiting earlier candidates guarantees each multiset is generated once.
- Sorting the candidates lets you break early once one exceeds the remainder. If only the count were needed, unbounded-knapsack DP would be O(n · target).