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.
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.
1 <= candidates.length <= 301 <= target <= 40The 'unlimited reuse of the same element' requirement is the key difference from Subsets/Permutations — it changes exactly one line in the recursive call.
Prune the moment the running sum exceeds target — no point continuing down a branch that's already invalid.
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.
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates); // enables the early-break optimization below
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; }
for (int i = start; i < candidates.length; i++) {
if (candidates[i] > remaining) break; // sorted array — every later candidate is even bigger, stop entirely
current.add(candidates[i]);
backtrack(candidates, remaining - candidates[i], i, current, result); // 'i', NOT 'i + 1' — allows reusing the SAME element
current.remove(current.size() - 1);
}
}Time: O(n^(target/min_candidate)) roughly — exponential, pruned heavily by the sorted early-break · Space: O(target/min_candidate) recursion depth