Combination Sum II

01 · Question

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.

Note: The solution set must not contain duplicate combinations.

Candidates and target are positive integers.

02 · Analysis

Sort positive candidates, choose indices in increasing order, and recurse at i+1 so each occurrence is used once. Skip equal values only at the same decision depth; deeper levels may still use another equal occurrence. Stop scanning when a candidate exceeds the remaining positive target. Worst-case enumeration including copies is O(n*2^n), plus O(n log n) sorting; auxiliary path/stack space is O(n), excluding output.

03 · Solution

Reference solution

1def combinationSum2(candidates: List[int], target: int) -> List[List[int]]:
2    candidates.sort()
3    res = []
4
5    def dfs(i, cur, total):
6        if total == target:
7            res.append(cur.copy())
8            return
9        if total > target or i == len(candidates):
10            return
11
12        # Include candidates[i]
13        cur.append(candidates[i])
14        dfs(i + 1, cur, total + candidates[i])
15        cur.pop()
16
17        # Skip candidates[i] and all duplicates
18        while i + 1 < len(candidates) and candidates[i] == candidates[i + 1]:
19            i += 1
20        dfs(i + 1, cur, total)
21
22    dfs(0, [], 0)
23    return res

Letter Combinations of a Phone Number

Unique Paths III