Combination Sum II
- 3 min read
- LC-Medium
- Backtracking
3 years ago
Solution
- Similar to Combination Sum, but each number in the array should only be used once.
- The problem here is that unlike Combination Sum I, the array has duplicates here. If you remember, Comb. Sum I had only distinct integers.
- This is a problem because for Example 1 above, if we use the same approach as Combination Sum I, we might end up with two answers [1, 7] and [7, 1]. These are duplicates. Only one of these is valid. Another wrong possibility is [1, 2, 5] and [2, 1, 5]
- To account for duplicate combinations, we do the following:
- Sort the array.
- At each point, make two decisions:
- Include the current number in the sum, and move on to the next index
- Skip index until the next number is not equal to the current number. And when recurring, increment index and don't include current number in the sum.
- gBasically, we're saying that out of the two decisions we make at each point, the right subtree will never have a duplicate, i.e. if current number is 1, the right subtree, won't have 1. We do this by using a while loop after sorting the array and skipping indices.
- In other words, if we choose to include a number in the left subtree, the right subtree should not have any instances of that number.
- Important: The above point doesn't get rid of any possibilities which include two of the same numbers. I.e. [1, 1, 6]. You might think the logic above won't account for the second 1, but remember that we only do the skipping of duplicate numbers on the right subtree. The left subtree will still include the second one. This is because we make two decisions at any point: include current number or skip current number. After sorting, imagine we include the first 1. The right subtree will skip the next one but in our next decision, the left subtree will include the second 1.
| Time | Space | Explanation |
|---|---|---|
O() | O() |
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
ans = []
def dfs(i, cur_sum, sub):
if cur_sum == target:
ans.append(sub)
return
if i == len(candidates) or cur_sum > target:
return
dfs(i + 1, cur_sum + candidates[i], sub + [candidates[i]])
while i + 1 < len(candidates) and candidates[i] == candidates[i + 1]:
i += 1
dfs(i + 1, cur_sum, sub)
dfs(0, 0, [])
return ans