这一题的思路是,首先需要排序,因为数字不可以重复,所以只能往后面找数字,同时因为candidates本身是有可能有重复的,所以在同一个位置上,需要判断一下是不是重复,重复就没有必要再来加一次了。
class Solution(object):
def combinationSum2(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
candidates.sort()
res = []
self.surpport(0, candidates, target, [], 0, res)
return res
def surpport(self, start, candidates, target, temp, count, res):
if count == target:
res.append(temp)
return
elif count > target:
return
else:
new = []
for i in range(start, len(candidates)):
if i > 0 and candidates[i-1] in new and candidates[i] == candidates[i-1]:
continue
new.append(candidates[i])
self.surpport(i+1, candidates, target, temp + [candidates[i]], count+candidates[i], res)