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
def combinationSum2(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, far past any feasible budget, and with many equal values most of that work regenerates the same multiset repeatedly.
Approach 2 — Sort + skip duplicate siblings
Duplicate output comes from duplicate values starting interchangeable branches. Sort the array so equal values are adjacent. Two rules in the per-level choice loop remove all redundancy: (1) after choosing index i, recurse from i + 1, which enforces single use; (2) within one level, if candidates[i] == candidates[i-1] and i > start, skip i, because a branch starting with the second copy of a value generates 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, a depth-first search over partial solutions with undo, plus the sorted-duplicate skip.
from typing import List
def combinationSum2(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
The recursion tree on the sorted array [1,2,2,2,5] (target 5), where each node is one choice at a level:
flowchart TD
A["start rem=5"] --> B["take 1, rem=4"]
A --> C["take 2, rem=3"]
A --> D["take 5, rem=0 — record [5]"]
B --> E["take 2, rem=2"]
E --> F["take 2, rem=0 — record [1,2,2]"]
E --> G["next 2: skip, duplicate sibling"]
C --> H["take 2, rem=1: overshoot, prune"]
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 2s | [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 real decision is not 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, so no skip rule is needed.
from collections import Counter
from typing import List
def combinationSum2(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.