Combination Sum II

mediumBacktracking198 stepsJava · Python · C++

Each candidate can be used once and the input has duplicates. Sort, recurse with i + 1, and skip a candidate equal to the previous one at the same level so identical combinations aren't produced twice.

▶ Watch the animated trace

Traced input: candidates = [10, 1, 2, 7, 6, 1, 5], target = 8 → [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]. Original problem: neetcode.io/problems/combination-target-sum-ii

Complexity

BestO(2ⁿ)

Averageexponential

WorstO(n·2ⁿ)

SpaceO(n)

Pruning by sorted order cuts most branches.

Key idea

Combines Subsets II (skip duplicates) with Combination Sum (target pruning).
i + 1 means each element is used at most once.
Break once candidates[i] > remain.

Common mistakes

Recursing with i allows reuse, which this problem forbids.
Skipping duplicates with i > 0 instead of i > start.

Solution

Java

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

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

Python

def combinationSum2(candidates: List[int], target: int) -> List[List[int]]:
    candidates.sort()
    res = []

    def find(start: int, remain: int, path: List[int]) -> None:
        if remain == 0:
            res.append(path[:])
            return
        for i in range(start, len(candidates)):
            if i > start and candidates[i] == candidates[i - 1]: continue
            if candidates[i] > remain: break
            path.append(candidates[i])
            find(i + 1, remain - candidates[i], path)
            path.pop()

    find(0, target, [])
    return res

C++

void find2(vector<int>& c, int start, int remain, vector<int>& path, vector<vector<int>>& res) {
    if (remain == 0) {
        res.push_back(path);
        return;
    }
    for (int i = start; i < (int)c.size(); i++) {
        if (i > start && c[i] == c[i - 1]) continue;
        if (c[i] > remain) break;
        path.push_back(c[i]);
        find2(c, i + 1, remain - c[i], path, res);
        path.pop_back();
    }
}

vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    sort(candidates.begin(), candidates.end());
    vector<vector<int>> res;
    vector<int> path;
    find2(candidates, 0, target, path, res);
    return res;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Duplicates allowed in one combination The two 1s are different elements.	`candidates = [1, 1, 2], target = 2`	`[[1, 1], [2]]`
No combination Nothing sums to 4.	`candidates = [3, 5], target = 4`	`[]`
Many duplicates [1, 2, 2] appears once even though there are three 2s.	`candidates = [2, 5, 2, 1, 2], target = 5`	`[[1, 2, 2], [5]]`