leetcode39、40:组合总和
leetcode39:组合总和
思路:采用回溯法
注意,回溯法是经常用到的算法,可以按照下面的模板来写
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
res =[]
def helper(arr,s,tmp):
#递归边界
if s == 0:
res.append(tmp)
return
elif s < 0:
return
for i in range(len(arr)):
if arr[i] > s: #剪枝
break
helper(arr[i:],s-arr[i],tmp+[arr[i]]) #该元素可以重复使用
helper(candidates,target,[])
return res
leetcode40:组合总和 II
思路:和39题不同之处在于每个元素不能被重复使用,那么需要在遍历时加上一些判定条件去重。
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
res = []
def dfs(arr,s,tmp):
if s == 0:
res.append(tmp)
return
if s < 0:
return
for i in range(len(arr)):
#添加一层去重
if i > 0 and arr[i] == arr[i-1]:
continue
if arr[i] > s:
break
dfs(arr[i+1:],s-arr[i],tmp+[arr[i]]) #同时该元素不能重复使用,所以要剔除
dfs(candidates,target,[])
return res