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.

02 · 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