75.Combination Sum II

MediumBacktracking · 5/9

Problem

Given a collection of candidate numbers candidates (which may contain duplicates) and a target, find all unique combinations where the chosen numbers sum to target.

Each number in candidates may be used at most once per combination, and the result must not contain duplicate combinations.

Examples

Input:  candidates = [10, 1, 2, 7, 6, 1, 5], target = 8
Output: [[1,1,6], [1,2,5], [1,7], [2,6]]
Explanation: Two different 1s exist, so [1,1,6] is allowed, but [1,7] appears only once.

Input:  candidates = [2, 5, 2, 1, 2], target = 5
Output: [[1,2,2], [5]]

Constraints

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

💡 Key Insight

This is Combination Sum (pick from start, prune when too big) combined with the Subsets II duplicate rule. After sorting, recurse with i + 1 (each element once) and, at a single level of the tree, skip candidates[i] when i > start && candidates[i] == candidates[i - 1]. Sorting also enables break once a candidate exceeds the remaining target.

Brute Force with a Set

TimeO(n · 2^n)SpaceO(n · 2^n) worst case for the set; O(n) recursion depth.

Intuition

Sort, then explore include/skip for every index, recording combinations that hit the target. Different indices with equal values create duplicate combinations, so dedupe with a Set<List<Integer>> (sorting makes equal combinations produce identical lists). Branches stop when the sum overshoots, but duplicates are still explored repeatedly.

Algorithm

Sort candidates.
dfs(i, remaining): if remaining == 0, add a copy of path to the set; if remaining < 0 or i == n, return.
Take candidates[i] → dfs(i + 1, remaining - candidates[i]); then skip → dfs(i + 1, remaining).
Return the set as a list.

Visualization

sorted = [1,1,2,5,6,7,10], target = 8

take 1(i=0), skip 1(i=1), skip 2, skip 5, ... take 7  -> [1,7]  add
skip 1(i=0), take 1(i=1), ... take 7                    -> [1,7]  already in set

Code

java

import java.util.*;

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

    private void dfs(int[] cand, int i, int remaining, List<Integer> path, Set<List<Integer>> found) {
        if (remaining == 0) {
            found.add(new ArrayList<>(path)); // set removes repeated combinations
            return;
        }
        if (remaining < 0 || i == cand.length) return;
        path.add(cand[i]);                          // take cand[i] once
        dfs(cand, i + 1, remaining - cand[i], path, found);
        path.remove(path.size() - 1);
        dfs(cand, i + 1, remaining, path, found);   // skip cand[i]
    }
}

Complexity

Time: O(n · 2^n) — every subset can be explored and copied; inputs with many equal values (e.g. lots of 1s) explore the same combination many times and can time out.
Space: O(n · 2^n) worst case for the set; O(n) recursion depth.

Sorted Backtracking with Skip and PruningOptimal

TimeO(n · 2^n) worst caseSpaceO(n)

Intuition

Loop over choices for the next element. Because the array is sorted, the first occurrence of a value at a given level already explores every combination that the later equal values could produce, so skip later equal values at that level. Recursing with i + 1 makes each element usable once, and break stops when candidates[i] > remaining.

Algorithm

Sort candidates.
backtrack(start, remaining):
- If remaining == 0, record a copy of path, return.
- For i from start to n - 1:
  - If i > start and candidates[i] == candidates[i - 1], continue.
  - If candidates[i] > remaining, break.
  - Push, backtrack(i + 1, remaining - candidates[i]), pop.

Visualization

flowchart TD
    R["rem=8 []<br/>sorted [1,1,2,5,6,7,10]"] -->|"1 i=0"| A["rem=7 [1]"]
    R -.->|"1 i=1 skip"| S["duplicate"]
    R -->|"2"| B["rem=6 [2]"]
    A -->|"1 i=1"| A1["rem=6 [1,1]"]
    A -->|"2"| A2["rem=5 [1,2]"]
    A -->|"7"| A3["rem=0 [1,7] ✓"]
    A1 -->|"6"| A11["rem=0 [1,1,6] ✓"]
    A2 -->|"5"| A21["rem=0 [1,2,5] ✓"]
    B -->|"6"| B1["rem=0 [2,6] ✓"]

Code

java

import java.util.*;

class Solution {
    private final List<List<Integer>> result = new ArrayList<>();
    private final List<Integer> path = new ArrayList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        backtrack(candidates, 0, target);
        return result;
    }

    private void backtrack(int[] cand, int start, int remaining) {
        if (remaining == 0) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < cand.length; i++) {
            if (i > start && cand[i] == cand[i - 1]) {
                continue; // same value already used to start a branch at this level
            }
            if (cand[i] > remaining) {
                break;    // sorted: nothing further can fit
            }
            path.add(cand[i]);
            backtrack(cand, i + 1, remaining - cand[i]); // i + 1: each element once
            path.remove(path.size() - 1);
        }
    }
}

Complexity

Time: O(n · 2^n) worst case — each distinct combination is visited once and copied in O(n); pruning makes it far faster in practice.
Space: O(n) — recursion depth and path (output excluded).

Complexity Comparison

Approach	Time	Space
Brute Force + Set	O(n · 2^n)	O(n · 2^n)
Backtracking with Skip + Pruning	O(n · 2^n) worst, heavily pruned	O(n)

Common Pitfalls

Recursing with i instead of i + 1 — that allows reusing the same element (that is Combination Sum I).
Using i > 0 instead of i > start in the skip — that blocks valid combos like [1,1,6].
Putting the skip check after the break is fine, but forgetting to sort makes both the skip and the break incorrect.
Using a set of unsorted lists for deduplication — [1,7] and [7,1] would both survive.