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

相似题型：

leetcode46：全排列