Combination Sum II

MediumBacktracking · Duplicate Skipping🧩 Backtracking LeetCode #40 ↗Updated Oct 30, 2026

Problem

Given an array candidates that may contain repeated values and a target, return every distinct combination whose sum is target. Each array element may be used at most once, and the answer must not list the same multiset of values twice (in any order).

Inputcandidates = [3,1,3,5,1,1], target = 8Output[[1,1,1,5],[1,1,3,3],[3,5]]

Inputcandidates = [2,2,2], target = 4Output[[2,2]]

Inputcandidates = [4,1], target = 2Output[]

1 ≤ n ≤ 100 · 1 ≤ candidates[i] ≤ 50 · 1 ≤ target ≤ 30

Try it yourself

Java

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Sort, then at each recursion level use a value only the first time it appears as the next pick (i > start && c[i] == c[i-1] → skip). Equal values can still stack down the tree, but never repeat across siblings — that is exactly what creates duplicate answers.

PatternBacktracking

Instinct Return ALL combinations, permutations, partitions or placements - or ask if any arrangement works - build a candidate step by step and undo each choice.

Memory hack Choose, explore, un-choose - walk the decision tree and snip a branch the moment it can no longer succeed.

Open the Backtracking guide →

Approaches

Brute ForceEvery Subset + Set Dedup

Time O(2ⁿ · n)Space O(2ⁿ · n)

Walk the full include/exclude tree over all 2ⁿ subsets. Whenever a subset sums to the target, sort a copy and insert it into a Set, so the two [1,7]s coming from different 1s collapse into one.

Java

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    Set<List<Integer>> seen = new HashSet<>();
    subsets(candidates, 0, 0, target, new ArrayList<>(), seen);
    return new ArrayList<>(seen);
}
private void subsets(int[] c, int i, int sum, int target, List<Integer> path,
                     Set<List<Integer>> seen) {
    if (i == c.length) {
        if (sum == target) {
            List<Integer> key = new ArrayList<>(path);
            Collections.sort(key);
            seen.add(key);
        }
        return;
    }
    path.add(c[i]); // take c[i]
    subsets(c, i + 1, sum + c[i], target, path, seen);
    path.remove(path.size() - 1);
    subsets(c, i + 1, sum, target, path, seen); // skip c[i]
}

Correct, but explores every subset even after the sum is far past the target.

BetterSorted Include/Exclude with Pruning

Time O(2ⁿ · n)Space O(n + answers · n)

Sort first so paths come out already ordered (no per-answer sort), and stop a branch as soon as remain hits 0 or the next value exceeds it — all later values are bigger. Duplicates are still produced (e.g. from different copies of 1) and filtered by a Set.

Java

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    int[] c = candidates.clone();
    Arrays.sort(c);
    Set<List<Integer>> seen = new LinkedHashSet<>();
    dfs(c, 0, target, new ArrayList<>(), seen);
    return new ArrayList<>(seen);
}
private void dfs(int[] c, int i, int remain, List<Integer> path, Set<List<Integer>> seen) {
    if (remain == 0) {
        seen.add(new ArrayList<>(path)); // already sorted
        return;
    }
    if (i == c.length || c[i] > remain) return; // sorted: nothing further fits
    path.add(c[i]);
    dfs(c, i + 1, remain - c[i], path, seen);
    path.remove(path.size() - 1);
    dfs(c, i + 1, remain, path, seen);
}

Pruning cuts most of the tree, but duplicate branches are still explored then discarded.

OptimalSorted Backtracking, Skip Equal Siblings

Time O(2ⁿ · n)Space O(n)

Each recursion level chooses the next element from c[start..]. Picking the second of two equal values at the same level would only rebuild a combination the first one already produced, so skip it; recurse with i + 1 since each element is single-use. Duplicates are never generated, so no set is needed.

Java

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    int[] c = candidates.clone();
    Arrays.sort(c);
    List<List<Integer>> res = new ArrayList<>();
    backtrack(c, 0, target, new ArrayList<>(), res);
    return res;
}
private void backtrack(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; // same value already tried here
        if (c[i] > remain) break;                    // sorted: the rest are too big
        path.add(c[i]);
        backtrack(c, i + 1, remain - c[i], path, res); // i + 1: use each element once
        path.remove(path.size() - 1);
    }
}

Same worst case on paper, but no duplicate branches and no hashing — the expected answer.

Pro tip

The condition is i > start, not i > 0 — otherwise you forbid [1,1,3,3] by skipping the second 1 one level down.

At a glance

Level	Approach	Time	Space
Brute Force	Every Subset + Set Dedup	`O(2ⁿ · n)`	`O(2ⁿ · n)`
Better	Sorted Include/Exclude with Pruning	`O(2ⁿ · n)`	`O(n + answers · n)`
Optimal	Sorted Backtracking, Skip Equal Siblings	`O(2ⁿ · n)`	`O(n)`

Common pitfalls

Skipping with i > 0 instead of i > start — loses answers like [1,1,1,5].
Forgetting to sort — equal values are not adjacent, so the skip check does nothing.
Recursing with i (Combination Sum I habit) — reuses the same element.

Interview tips

Explain the skip as “one branch per distinct value per level”.
Draw the tree for [1,1,1,5] / 7 to show why i > start keeps [1,1,5].
Contrast with Combination Sum I (i vs i + 1) and Subsets II.

Pattern

Sorted backtracking with sibling de-dup → combinations from an input with duplicates where each element is used once.

My notes saved in this browser