Given a collection of candidate numbers (C) and a target number (T),
find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Example
Given candidate set [10,1,6,7,2,1,5] and target 8,
A solution set is:
[
[1,7],
[1,2,5],
[2,6],
[1,1,6]
]
这个题最难的地方在于如何处理重复数字
如果不去重，就会出现1(1), 2, 5, 1(2), 2, 5 的情况
解决办法就是
只有看到1(1) 在结果中时才使用1(2)
这样这个1(2), 2, 5就不会出现，而1, 1, 6会出现
⚠️如果直接在看到重复数字就跳过，那么1,1,6就不会出现了
code
class Solution:
"""
@param candidates: Given the candidate numbers
@param target: Given the target number
@return: All the combinations that sum to target
"""
def combinationSum2(self, candidates, target):
candidates.sort() # sort it first !
self.result = []
used = [False] * len(candidates)
self.dfsHelper(candidates, target, [], 0, used)
return self.result
# @param: candidates: list, target: int, path: list, index: int
# @return: None
def dfsHelper(self, candidates, target, path, index, used):
# base
if target == 0:
self.result.append(list(path))
return
if target < 0:
return
# divide
for i in range(index, len(candidates)):
# only use the following same number when previous same number is used
if i != 0 and candidates[i] == candidates[i - 1]:
if not used[i - 1]:
continue
path.append(candidates[i])
used[i] = True
self.dfsHelper(candidates, target - candidates[i], path, i + 1, used)
used[i] = False
path.pop()
