Combination Sum II

Problem Description

Given a collection of candidate numbers candidates and a target number target, find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

The solution set must not contain duplicate combinations.

Examples

Constraints

• 1 ≤ candidates.length ≤ 100
• 1 ≤ candidates[i] ≤ 50
• 1 ≤ target ≤ 30

The Duplicate Problem Is Structural, Not Accidental

The core tension in this problem is that the input can have duplicate values, but the output cannot have duplicate combinations. The brute-force instinct is to use a set to deduplicate results after generating everything, but that masks the actual insight the problem tests.

Sort the array first. Once sorted, duplicate values are adjacent. In your backtracking loop, if you’re about to pick a value that’s the same as the one you just tried at this recursion depth, skip it. That one check prevents you from ever generating a duplicate combination in the first place, which is far cleaner and faster than post-processing.

Solution: Backtracking with Duplicate Skip

import java.util.*;

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates); // sorting makes duplicate-skipping work
        List<List<Integer>> result = new ArrayList<>();
        backtrack(candidates, target, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int[] candidates, int remaining, int start,
                            List<Integer> current, List<List<Integer>> result) {
        if (remaining == 0) {
            result.add(new ArrayList<>(current));
            return;
        }

        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] > remaining) break; // sorted, so nothing after helps

            // skip duplicates at the same recursion depth
            if (i > start && candidates[i] == candidates[i - 1]) continue;

            current.add(candidates[i]);
            backtrack(candidates, remaining - candidates[i], i + 1, current, result);
            current.remove(current.size() - 1);
        }
    }
}

class Solution:
    def combinationSum2(self, candidates: list[int], target: int) -> list[list[int]]:
        candidates.sort()  # sorting makes duplicate-skipping work
        result = []

        def backtrack(start: int, remaining: int, current: list[int]):
            if remaining == 0:
                result.append(current[:])
                return

            for i in range(start, len(candidates)):
                if candidates[i] > remaining:
                    break  # sorted, so nothing after helps

                # skip duplicates at the same recursion depth
                if i > start and candidates[i] == candidates[i - 1]:
                    continue

                current.append(candidates[i])
                backtrack(i + 1, remaining - candidates[i], current)
                current.pop()

        backtrack(0, target, [])
        return result

#include <vector>
#include <algorithm>

class Solution {
public:
    std::vector<std::vector<int>> combinationSum2(std::vector<int>& candidates, int target) {
        std::sort(candidates.begin(), candidates.end());
        std::vector<std::vector<int>> result;
        std::vector<int> current;
        backtrack(candidates, target, 0, current, result);
        return result;
    }

private:
    void backtrack(std::vector<int>& candidates, int remaining, int start,
                   std::vector<int>& current, std::vector<std::vector<int>>& result) {
        if (remaining == 0) {
            result.push_back(current);
            return;
        }

        for (int i = start; i < (int)candidates.size(); i++) {
            if (candidates[i] > remaining) break;

            // skip duplicates at the same recursion depth
            if (i > start && candidates[i] == candidates[i - 1]) continue;

            current.push_back(candidates[i]);
            backtrack(candidates, remaining - candidates[i], i + 1, current, result);
            current.pop_back();
        }
    }
};

Complexity Analysis:

• Time Complexity: O(2^n) in the worst case, where every subset is explored. The duplicate-skip prune cuts this significantly in practice.
• Space Complexity: O(target / min_candidate) for the maximum recursion depth.

Where it breaks: the condition i > start is critical. If you write i > 0 instead, you’d skip valid combinations. For example, with candidates = [1,1,2] and target = 3, you need both 1s. The check i > start ensures you only skip a duplicate if you’re at the same choice point, not if it’s a genuinely new one deeper in the tree.

Why Not Just Use a Set to Deduplicate?

You can, and it works. But it generates far more subsets before filtering, which costs more time and memory. With target = 30 and small candidates, the set approach can generate thousands of duplicates that a sorted skip avoids entirely.

Common Mistakes

• Using i > 0 instead of i > start for the duplicate check. This incorrectly skips valid combinations that use the same value at different recursion levels.
• Passing i instead of i + 1 to the recursive call. Each candidate can only be used once, so the next call must start after the current index.
• Not sorting first. The duplicate-skip logic only works when equal values are adjacent.

Frequently Asked Questions

How is this different from Combination Sum? In Combination Sum, each number can be reused unlimited times (you recurse with the same i). Here, each number is used at most once (you recurse with i + 1).

What if I need to count combinations instead of list them? That becomes a 2D DP problem (similar to Coin Change II). Backtracking is for when you need the actual combinations, not just the count.

← All Problems