Combination Sum
Problem
Given a list of distinct positive integers candidates and a target, return all unique combinations where the chosen numbers sum to target. The same number may be chosen from candidates an unlimited number of times.
Examples
Example 1
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation: 2+2+3=7 (2 reused) and 7 alone both work.
Constraints
- •
1 <= candidates.length <= 30 - •
1 <= target <= 40
Hints
Hint 1
The 'unlimited reuse of the same element' requirement is the key difference from Subsets/Permutations — it changes exactly one line in the recursive call.
Hint 2
Prune the moment the running sum exceeds target — no point continuing down a branch that's already invalid.
Hint 3
Sorting candidates first lets you break out of the loop entirely once a candidate alone would exceed the remaining target, rather than checking every remaining candidate individually.
Solutions
public List<List<Integer>> combinationSumBruteForce(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
backtrack(candidates, target, 0, new ArrayList<>(), result);
return result;
}
private void backtrack(int[] candidates, int remaining, int start, List<Integer> current, List<List<Integer>> result) {
if (remaining == 0) { result.add(new ArrayList<>(current)); return; }
if (remaining < 0) return; // overshoot — prune, but only AFTER trying (no early break, since candidates aren't sorted)
for (int i = start; i < candidates.length; i++) {
current.add(candidates[i]);
backtrack(candidates, remaining - candidates[i], i, current, result);
current.remove(current.size() - 1);
}
}Time: Exponential, less pruned than the sorted version · Space: O(target/min_candidate) recursion depth