38. Combination Sum II

Sort the candidates so duplicates are adjacent and pruning is possible. Each element may be used once (recurse from i+1), and at each level skip a value equal to its left neighbour to avoid duplicate combinations.

Two rules make it work

1. Each number used once: recurse from i + 1, never i.
2. No duplicate combinations: after sorting, skip index i when i > start and candidates[i] == candidates[i-1] — the same value already led a branch at this level.

Sorting also enables pruning: once candidates[i] > remaining, every later (larger) candidate also overflows, so break.

Walk-through

1. Sort candidates.
2. Backtrack with a running remaining = target:
   • If remaining == 0, record path.
   • For i in [start, n): skip duplicates as above; break if candidates[i] > remaining; else include it, recurse from i+1 with remaining - candidates[i], then undo.

Worked example

candidates = [10,1,2,7,6,1,5], target = 8 → sorted [1,1,2,5,6,7,10]:

• [1,7], [1,2,5], [2,6], [1,1,6].

Result: [[1,1,6],[1,2,5],[1,7],[2,6]].

Complexity

• Time: O(2^n) combinations in the worst case.
• Space: O(n) recursion depth.

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

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

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