DSA problem
Combination Sum
Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. The same number from candidates may be chosen an unlimited number of times. Two combinations are considered unique if the frequency of at least one of the chosen numbers is different.
What makes this different from a plain subsets problem is the "unlimited reuse" rule: a number may appear in a combination as many times as needed. So with candidates = [2, 3, 6, 7] and target = 7, the answer includes both [2, 2, 3] (using 2 twice) and [7] (using 7 once), but does not include both [2, 2, 3] and [3, 2, 2] because they are the same combination.
The canonical approach is backtracking with two parameters: a start index that prevents re-considering earlier candidates (which is what dedupes orderings) and a remaining value that tracks how much of target is still unaccounted for. At each call we iterate i from start to n - 1; if candidates[i] > remaining we prune (unsorted: just continue; sorted: break because nothing later can fit either).
The crucial recursive twist is that when we pick candidates[i], we recurse with the same start = i rather than i + 1 — that is how a single index is allowed to be reused across multiple draws while still preventing different orderings of the same multiset. When remaining == 0 we snapshot a copy of path into the results. Worst-case time is bounded by O(N^(target / min)) where N is the number of candidates; space is O(target / min) for recursion.
Examples
candidates = [2,3,6,7], target = 7[[2,2,3],[7]]candidates = [2,3,5], target = 8[[2,2,2,2],[2,3,3],[3,5]]candidates = [2], target = 1[]Constraints
- 1 <= candidates.length <= 30
- 2 <= candidates[i] <= 40
- All elements of candidates are distinct.
- 1 <= target <= 40
- The number of unique combinations for the given input is guaranteed to be fewer than 150.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.