Combination Sum II — InterviewPrepKit

Solving tips

Two differences from Combination Sum I drive the solution: each element is single-use (recurse with i+1) and duplicate values must not spawn duplicate combinations.
Sort first, then in the per-level loop skip candidates[i] when i > start and candidates[i] == candidates[i-1]: this suppresses duplicate sibling branches while still allowing repeated values along a path.
Use i > start (not i > 0) for the skip, or you wrongly drop valid answers like [1,1,6] where a value repeats within one path.
Worst case is O(2^n) time with O(n) space; the sorted break plus duplicate-skip prune aggressively so it never approaches 2^100.

Problem

You are given an array candidates of positive integers — duplicates allowed this time — and a positive integer target. Return every unique combination of candidates that sums to exactly target, where each array element may be used at most once. Two occurrences of the same value are different elements (each usable once), but combinations that read the same as multisets count as one: the output must not contain the same combination twice. Any order of combinations is fine.

Examples

candidates = [10,1,2,7,6,1,5], target = 8 → [[1,1,6],[1,2,5],[1,7],[2,6]] — note [1,7] appears once even though there are two 1s that could pair with 7.
candidates = [2,5,2,1,2], target = 5 → [[1,2,2],[5]] — three 2s exist but a combination may use at most the multiplicities present.
candidates = [3,3], target = 6 → [[3,3]] — both copies used, each once.

Constraints

1 <= len(candidates) <= 100
1 <= candidates[i] <= 50
1 <= target <= 30

With up to 100 elements, anything that enumerates all 2^100 subsets is hopeless — the duplicate values are what let you collapse the search space.

Think about it first

Hint 1

This differs from Combination Sum in two ways: each element is single-use (recurse past it, not on it), and equal values exist. Which of the two actually causes duplicate output?

Hint 2

Sort the array. Now equal values sit together. If at some tree depth you start a branch with the first `1` and later start a sibling branch with the second `1`, those two branches generate identical combination sets. When is choosing a duplicate value safe, and when is it redundant?

Hint 3

In the loop over choices at one recursion level, skip candidates[i] when i > start and candidates[i] == candidates[i-1]: using a duplicate is fine when it directly follows its twin in the path (deeper level), but starting a fresh sibling branch with it repeats work. Add the sorted-overshoot break and the search collapses.

TL;DR

Sort, then backtrack with a start index, skipping same-value siblings at each level — O(2^n) worst-case time, O(n) space beyond the output.

Approach 1 — Brute force

Each element is in or out: enumerate all subsets, keep those summing to target, and deduplicate at the end with a set of sorted tuples.

from typing import List


class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        found: set[tuple[int, ...]] = set()
        n = len(candidates)

        def explore(i: int, remaining: int, path: List[int]) -> None:
            if remaining == 0:
                found.add(tuple(sorted(path)))
                return
            if i == n or remaining < 0:
                return
            explore(i + 1, remaining, path)          # exclude candidates[i]
            path.append(candidates[i])
            explore(i + 1, remaining - candidates[i], path)  # include it
            path.pop()

        explore(0, target, [])
        return [list(t) for t in found]

Complexity: O(2^n · n) time, O(n) recursion space. At n = 100 that is 2^100 subsets — astronomically past any budget — and with many equal values most of that work regenerates the same multiset over and over.

Approach 2 — Sort + skip duplicate siblings

The insight: duplicate output comes from duplicate values starting interchangeable branches. Sort the array so equal values are adjacent. In the per-level choice loop, two rules kill all redundancy: (1) after choosing index i, recurse from i + 1 — single use; (2) within one level, if candidates[i] == candidates[i-1] and i > start, skip i — a branch starting with the second copy of a value would generate exactly the combinations the first copy’s branch already generated. Taking the twin inside a path (when i == start) stays legal, which is how [1,1,6] survives. This is standard backtracking — depth-first search over partial solutions with undo — plus the classic sorted-duplicate-skip.

from typing import List


class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates = sorted(candidates)
        result: List[List[int]] = []
        path: List[int] = []

        def backtrack(start: int, remaining: int) -> None:
            if remaining == 0:
                result.append(path.copy())
                return
            for i in range(start, len(candidates)):
                if i > start and candidates[i] == candidates[i - 1]:
                    continue              # same value already led this level
                c = candidates[i]
                if c > remaining:
                    break                 # sorted: all later values overshoot too
                path.append(c)
                backtrack(i + 1, remaining - c)   # i + 1: single use
                path.pop()

        backtrack(0, target)
        return result

Walkthrough on candidates = [2,5,2,1,2], target = 5 — sorted: [1,2,2,2,5]:

level choice	path	remaining	outcome
take `1` (i=0)	`[1]`	4	recurse from i=1
take `2` (i=1)	`[1,2]`	2	recurse from i=2
take `2` (i=2, `i == start`)	`[1,2,2]`	0	record `[1,2,2]`
back at i=2 level, i=3 is another `2`	`[1,2]`	2	skipped (`i > start`, equal twin)
back under `[1]`, i=2 and i=3 are `2`s	`[1]`	4	skipped as duplicate siblings; `5 > 4` → break
top level, take `2` (i=1)	`[2]`	3	`2,2` path leaves −1 → break; siblings skipped
top level i=2, i=3	—	—	duplicate `2` siblings skipped
take `5` (i=4)	`[5]`	0	record `[5]`

Result: [[1,2,2],[5]], each found exactly once.

Complexity: O(2^n) worst-case time (distinct values force a full subset tree), but the duplicate-skip and the sorted break prune aggressively in practice; O(n) space for path and recursion.

Approach 3 — Backtrack over value counts

The insight: the real decision isn’t per element but per value: for each distinct value with multiplicity m, choose how many copies (0..m) to take. Compressing the array into (value, count) pairs makes duplicate combinations structurally impossible — no skip rule needed.

from collections import Counter
from typing import List


class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        counts = sorted(Counter(candidates).items())
        result: List[List[int]] = []
        path: List[int] = []

        def backtrack(idx: int, remaining: int) -> None:
            if remaining == 0:
                result.append(path.copy())
                return
            if idx == len(counts) or counts[idx][0] > remaining:
                return                    # sorted: nothing ahead can fit
            value, avail = counts[idx]
            take = 0
            while take <= avail and value * take <= remaining:
                backtrack(idx + 1, remaining - value * take)
                path.append(value)
                take += 1
            for _ in range(take):         # undo all copies we stacked up
                path.pop()

        backtrack(0, target)
        return result

Walkthrough on [2,5,2,1,2], target = 5 — counts: [(1,1),(2,3),(5,1)]:

Take zero or one 1. With one 1 (remaining 4): take zero/one/two 2s → two 2s leaves 0 → record [1,2,2].
With zero 1s (remaining 5): 2s can’t land on 0 before overshooting except… 2·1 leaves 3, 2·2 leaves 1 — no; then value 5, one copy → record [5].

Complexity: same O(2^n) worst case (all values distinct degenerates to Approach 2), O(n) space. Worth knowing because “loop over how many copies” generalizes to bounded-knapsack-style problems.

Common pitfalls

Skipping with i > 0 instead of i > start — that also forbids [1,1,6]-style repeats within a path and drops valid answers.
Forgetting to sort first — the candidates[i] == candidates[i - 1] check only works when equal values are adjacent.
Recursing with i instead of i + 1 — reintroduces unlimited reuse from Combination Sum I.
Deduplicating output with a set instead of pruning the search — correctness survives but you still pay for every duplicate branch, which is exactly what blows up at n = 100.

Pattern takeaway

When the input contains duplicate values and answers are order-insensitive, sort and apply the sibling-skip rule: at any one recursion level, let each distinct value start at most one branch (i > start and a[i] == a[i-1] → skip), while still allowing repeats vertically along a path. This one idiom — identical here, in Subsets II, and in Permutations II — is the difference between pruning duplicates and generating-then-filtering them.