40. Combination Sum II
## description
## 40. Combination Sum II
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.
Example 1:
1Input: candidates = [10,1,2,7,6,1,5], target = 8
2Output:
3[
4[1,1,6],
5[1,2,5],
6[1,7],
7[2,6]
8]Example 2:
1Input: candidates = [2,5,2,1,2], target = 5
2Output:
3[
4[1,2,2],
5[5]
6]- –1 <= candidates.length <= 100
- –1 <= candidates[i] <= 50
- –1 <= target <= 30
Constraints:
## notes
### Intuition
For each number, we have two choices, use it or skip it. We also want to avoid using duplicates again.
### Implementation
We can solve this using recursing backtracking. Since we have two choices, we can recurse on both choices while traversing the array. In order to mitigate duplicates, we should also sort the array so that we can skip over all duplicates after using the first occurrence.
We initialize our result which will be a set to ensure there are no duplicate combinations.
The recursive function takes in the index, i, the current list of numbers, curr, in the combination and the total.
- –If total equals target, we add curr as a tuple to the result
- –If i exceeds the bounds or total is greater than target, we return early
- –Our first choice is to the use the current number, we add it to the curr and recurse with i + 1, curr and the total + candidates[i]
- –Our second choice is to skip the current number, so we pop it from curr
- –We also want to skip over all duplicates at this point, so we iterate while i + 1 < len(candidates) and candidates[i] = candidates[i + 1] and increment i
- –Then, we recurse with i + 1, curr and the total (unchanged because of skip)
Finally, we call the recursive function with i = 0 and empty array for curr and total = 0. For the result, we create the result by making the tuples into arrays.
- –Time: O(n * 2^n), we iterate over each number and we have two recursive choices at each number
- –Space: O(n), the recursive call stack will only be, at most, n.
### Complexity
## solution
1from typing import List
2
3class Solution:
4 def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
5 res = set()
6 candidates.sort() # O(n log n)
7 def recurse(i: int, curr: List[int], total: int):
8 if total == target:
9 res.add(tuple(curr))
10 return
11 if i >= len(candidates) or total > target:
12 return
13
14 # Case 1: Add the current number
15 curr.append(candidates[i])
16 recurse(i + 1, curr, total + candidates[i])
17
18 # Case 2: Skip the current number and all duplicates
19 curr.pop()
20
21 while i + 1 < len(candidates) and candidates[i] == candidates[i + 1]:
22 i += 1
23
24 recurse(i + 1, curr, total)
25
26 recurse(0, [], 0)
27 return [list(c) for c in res]
28
29
30
31if __name__ == "__main__":
32 # Include one-off tests here or debugging logic that can be run by running this file
33 # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
34 solution = Solution()
35