leetcode-40 组合总和
题目描述:
给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次。
注:和39题比,增加的难点主要在于有重复数字
解法一:回溯
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
self.res = []
candidates.sort(reverse=True)
self.find(candidates,target,0,[])
return self.res
def find(self,candidates,target,index,path):
if target == 0:
self.res.append(path[:])
return
prev = 0
for i in range(index,len(candidates)):
if candidates[i] != prev and candidates[i]<=target:
path.append(candidates[i])
self.find(candidates,target-candidates[i],i+1,path)
path.pop()
prev = candidates[i]
递归
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
self.res = []
candidates.sort(reverse=True)
self.find(candidates,target,0,[])
return self.res
def find(self,candidates,target,index,path):
if target < 0:
return
if target == 0:
self.res.append(path[:])
for i in range(index,len(candidates)):
if i > index and candidates[i] == candidates[i-1]:
continue
self.find(candidates,target-candidates[i],i+1,path+[candidates[i]])
注:体会递归与回溯的区别,回溯有push和pop这个过程?