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: Input: candidates = [10,1,2,7,6,1,5], target = 8 Output: [ [1,1,6], [1,2,5], [1,7], [2,6] ]
- code
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
res = []
def dfs(start, target, path):
if target < 0: return
elif target == 0:
res.append(path)
return
for i in range(start, len(candidates)):
# Very important here! We don't use `i > 0` because we always want
# to count the first element in this recursive step even if it is the same
# as one before. To avoid overcounting, we just ignore the duplicates
# after the first element.
if i > start and candidates[i] == candidates[i-1]: continue
dfs(i+1, target - candidates[i], path + [candidates[i]])
dfs(0, target, [])
return res