Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
Each number in candidates may only be used once in the combination.
It is very similar to combination sum I. But we have duplicate numbers here.
Duplicates numbers are allowed.
Modify from comb sum I
In the recursive call, we call
def dfs(self, nums, index, target, path):
if target < 0:
return
if target == 0:
self.all_path.append(path)
for i in range(index, len(nums)):
self.dfs(nums, i + 1, target - nums[i], path + [nums[i]])
The index is i + 1. That means later recursive call to dfs can only use numbers from index from i + 1 to end.
This makes sure each number is used only once. But can’t avoid duplicate.
EG: Input: candidates = [10,1,2,7,6,1,5], target = 8,
Our algorithm will return two [1,7].
One is the produced by first calling dfs(nums, 1, 7, [1]) then dfs(nums, 3, 0, [1,7]).
The other [1,7] is from dfs(nums, 3, 1, [7]), then dfs(nums, 5, 0, [7, 1]).
Root of the problem
The problem is because we used the same number at the same level. (Assume we sort the candidates first).
EG: Input: candidates = [1,1,7], target = 8,
At the same level of the tree, our previous algorithm will add two paths that starts with 1 to the solution by calling dfs(nums, 1, 7, [1]) and dfs(nums, 2, 7, [1]). This will generate duplicate.
Avoid the problem
Use a dict
We use a dictionary to record the numbers used at each level. And we only recurse when the number is not seen at that level.
Use pre and cur
since the input is sorted. We can just recurse when the previous num[i] is different from current nums[i]
def combinationSum2(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
candidates.sort()
self.dfs(candidates, 0, target, [])
return self.all_path
def dfs(self, nums, index, target, path):
if target < 0:
return
if target == 0:
self.all_path.append(path)
prev = None
for i in range(index, len(nums)):
cur = nums[i]
if prev != cur:
self.dfs(nums, i + 1, target - nums[i], path + [nums[i]])
prev = cur