37. Combination Sum

Build combinations by adding candidates and subtracting from the target. Allow reusing the current candidate (pass the same start index) so numbers can repeat, and use a start index to avoid generating the same multiset in different orders.

Idea

We explore combinations that sum to target, where each candidate can be reused. Two devices keep it correct and duplicate-free:

• Reuse: recurse with the same start index i, so a number can be picked again.
• Start index: never look at candidates before start, so [2,2,3] is generated but not its reorderings.

Sorting the candidates lets us prune: once a candidate exceeds the remaining target, all later (larger) ones do too, so we can stop the loop.

Algorithm

backtrack(start, path, remaining):

1. If remaining == 0, record a copy of path.
2. For i from start to end: if candidates[i] > remaining, break; else choose it, recurse with the same i and remaining - candidates[i], then un-choose.

Worked example: candidates = [2,3,6,7], target = 7

• 2+2+3 = 7 → [2,2,3].
• 7 → [7].

Result: [[2,2,3],[7]].

Complexity

• Time: exponential in the worst case (bounded by the number of combinations).
• Space: O(target / min candidate) recursion depth.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates);
        backtrack(candidates, 0, new ArrayList<>(), target, result);
        return result;
    }

    private void backtrack(int[] cand, int start, List<Integer> path, int remaining, List<List<Integer>> result) {
        if (remaining == 0) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < cand.length; i++) {
            if (cand[i] > remaining) {
                break;
            }
            path.add(cand[i]);
            backtrack(cand, i, path, remaining - cand[i], result);
            path.remove(path.size() - 1);
        }
    }
}