代码随想录算法训练营第二十九天| 回溯算法02

39. 组合总和

本题是 集合里元素可以用无数次，那么和组合问题的差别 其实仅在于 startIndex上的控制

题目链接/文章讲解：代码随想录

视频讲解：带你学透回溯算法-组合总和（对应「leetcode」力扣题目：39.组合总和）| 回溯法精讲！_哔哩哔哩_bilibili

对应组合可以写出来，注意startIndex以及剪枝tiaojian

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result=[]
        self.backtracking(candidates,target,0,[],result,0)
        return result
    def backtracking(self,candidates,target,startIndex,path,result,cur_sum):
        if cur_sum==target:
            result.append(path[:])
            return
        for i in range(startIndex,len(candidates)):
            if cur_sum+candidates[i]>target:
                continue
            path.append(candidates[i])
            self.backtracking(candidates,target,i,path,result,cur_sum+candidates[i])
            path.pop()

 40. 组合总和II

本题开始涉及到一个问题了：去重。

注意题目中给我们 集合是有重复元素的，那么求出来的 组合有可能重复，但题目要求不能有重复组合。

题目链接/文章讲解：代码随想录

视频讲解：回溯算法中的去重，树层去重树枝去重，你弄清楚了没？| LeetCode:40.组合总和II_哔哩哔哩_bilibili

 先排序，再剪枝

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        result=[]
        candidates.sort()
        self.backtracking(candidates,target,0,[],result,0)
        return result
    def backtracking(self,candidates,target,startIndex,path,result,cur_sum):
        if cur_sum==target:
            result.append(path[:])
            return
        for i in range(startIndex,len(candidates)):
            if i>startIndex and candidates[i]==candidates[i-1]:
                continue
            if cur_sum+candidates[i]>target:
                break
            path.append(candidates[i])
            self.backtracking(candidates,target,i+1,path,result,cur_sum+candidates[i])
            path.pop()