Combination Sum II

How it works

We need all unique combinations where each number can be used at most once, and duplicates in the input should not create duplicate combinations.

To handle duplicates safely, we:

1. Sort the array This groups equal numbers together, which helps us skip duplicates easily.

2. Use backtracking where at each index we decide:

   • Take the number
   • Skip the number

3. To avoid duplicate combinations:

   • If candidates[i] == candidates[i - 1] and we are still in the same level of recursion (i > idx), we skip that number.

4. We stop early if current_sum + candidates[i] > target because the list is sorted.

This approach explores each number only once per combination path and guarantees no repeated results.

Steps

1. Sort the candidates.
2. Define a DFS function dfs(idx, path, curSum):
   • If curSum == target, add a copy of path to the result.
   • Loop i from idx to end:
     • If i > idx and the current number equals the previous → skip (duplicate control).
     • If adding this number exceeds target → break (pruning).
     • Include the number and recurse with i + 1 (cannot reuse same element).
     • Backtrack by removing the last number.
3. Call dfs(0, [], 0) and return the result.

Complexity

• Time complexity: O(n * 2 ^ n)
• Space complexity: O(n)

Things to watch for

Generating Duplicate Combinations

The input contains duplicates, and each element can only be used once. Without proper duplicate handling, [1,1,2] with target 3 might produce [1,2] twice. Always sort first and skip consecutive duplicates at the same recursion level.

Reusing Elements (Using i Instead of i + 1)

Unlike Combination Sum I where elements can be reused, this problem requires each element to be used at most once. Recursing with the same index allows reuse.

Forgetting to Sort Before Skipping Duplicates

The duplicate-skipping logic candidates[i] == candidates[i-1] only works on a sorted array. Without sorting, duplicates won't be adjacent and the skip logic fails silently, producing duplicate combinations.

from typing import List

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

        def dfs(idx, path, cur):
            if cur == target:
                res.append(path.copy())
                return
            for i in range(idx, len(candidates)):
                if i > idx and candidates[i] == candidates[i - 1]:
                    continue
                if cur + candidates[i] > target:
                    break

                path.append(candidates[i])
                dfs(i + 1, path, cur + candidates[i])
                path.pop()

        dfs(0, [], 0)
        return res

class Solution {
public:
    vector<vector<int>> res;
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        res.clear();
        sort(candidates.begin(), candidates.end());
        dfs(0, {}, 0, candidates, target);
        return res;
    }

private:
    void dfs(int idx, vector<int> path, int cur, vector<int>& candidates, int target) {
        if (cur == target) {
            res.push_back(path);
            return;
        }
        for (int i = idx; i < candidates.size(); i++) {
            if (i > idx && candidates[i] == candidates[i - 1]) {
                continue;
            }
            if (cur + candidates[i] > target) {
                break;
            }

            path.push_back(candidates[i]);
            dfs(i + 1, path, cur + candidates[i], candidates, target);
            path.pop_back();
        }
    }
};