题目描述
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.
代码 (Python 3)
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
rst = []
self.ans = []
candidates = sorted(candidates)
self.solve(candidates, rst, target, 0)
return self.ans
def solve(self, cond, rst, target, start):
if target == 0:
if sorted(rst) not in self.ans:
temp = sorted(rst)
self.ans.append(temp)
else:
for i in range(start, len(cond)):
if i != start and cond[i] == cond[i - 1]:
continue
if cond[i] > target:
break
else:
rst.append(cond[i])
self.solve(cond, rst, target - cond[i], i + 1)
rst.remove(cond[i])
|