Combination Sum II

MediumBacktrackingNeetCode 150MidOpen on LeetCodeUpdated Nov 11, 2026

You're given an array of positive integers candidates, which may contain duplicates, and a positive target. Return every unique combination of candidates that adds up to target, using each element at most once. Combinations with the same values count as the same combination, whichever copies they use. The result may be in any order.

Examples

candidates = [3,1,3,5,1,1], target = 8 returns [[1,1,1,5],[1,1,3,3],[3,5]]

There are several ways to pick the two 3s or the 1s, but each multiset of values is listed once.

candidates = [4,2], target = 1 returns []

Every candidate is larger than the target.

candidates = [2,2,2], target = 4 returns [[2,2]]

Any two of the three 2s work, and they all give the same combination.

Constraints

1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30

Hints

Hint 1

Compared with Combination Sum, two rules change: each element is used once, and the input has duplicates. Handle them one at a time.

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Sort the candidates and backtrack with a start index, as in Combination Sum, with two changes. Recurse with i + 1 because each element can be used once. At each depth, skip index i when i > start and candidates[i] equals candidates[i - 1], so each distinct value is tried only once in each position. Sorting also lets the loop stop as soon as a candidate exceeds the remaining target. The worst case is O(2^n), and the recursion uses O(n) space besides the output.

Time

O(2^n)

Space

O(n)

Pitfall

Generating every combination and deduplicating afterward with a set. It returns the right answer, but explores the same branches once per arrangement of the duplicates, which blows up on inputs with many repeated values.

Solutions

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

    private void backtrack(int[] c, int start, int remaining, List<Integer> path, List<List<Integer>> out) {
        if (remaining == 0) {
            out.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] > remaining) break;
            path.add(c[i]);
            backtrack(c, i + 1, remaining - c[i], path, out);
            path.remove(path.size() - 1);
        }
    }
}

class Solution:
    def combinationSum2(self, candidates, target: int):
        candidates.sort()
        out = []
        path = []

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

        backtrack(0, target)
        return out