代码随想录算法训练营第二十三天| leetcode39. 组合总和、leetcode40.组合总和II、leetcode131.分割回文串

1 leetcode39. 组合总和

题目链接：39. 组合总和 - 力扣（LeetCode）

文章链接：代码随想录

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

思路：跟之前差不多，就是将他的循环改一下，但是我发现有重复的数值了，不知道如何删除

1.1 自己的思路

错误：

1. 基本思路是完全可以实现的，但是有重复的数值，不知道怎么删除，但是也就浅浅记录一下这个方法吧

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

1.2 视频的思路

看视频过程中然后反思自己的代码，做出来了

原因：索引的起始位置出现了错误，更改以后就正确了

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

1.3 剪枝的方法

class Solution:
    def __init__(self):
        self.result =[]
        self.path = []
        self.num = 0
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        self.backtracking(candidates,target,0)
        return self.result
    def backtracking(self,candidates,target,index):
        candidates.sort()
        if sum(self.path[:])>target:
            return
        if sum(self.path[:])==target:
            self.result.append(self.path[:])
            return self.result
        for i in range(index,len(candidates)):
            if target-candidates[i]<0:
                break
            self.path.append(candidates[i])
            self.backtracking(candidates,target,i)
            self.path.pop()

1.4 本题小结

1. 这道题我也算是真正自己做啦，就是当时忘记去重，不知道怎么加后来自己想了以后也写出来啦
2. 这道题的剪枝方法，我感觉排序会浪费时间，觉得没有优化太多

2 leetcode40.组合总和II

题目链接：40. 组合总和 II - 力扣（LeetCode）

文章链接：代码随想录

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

思路：照葫芦画瓢，结果发现我翻车了，就是有重复的

2.1 回溯的方法

这里的判断条件挺有意思的，从当前位置的后一个去比较，比较他们的值是否有重复的，然后进行去重，确实这个去重是我没有想到的地方

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

2.2 使用一个列表的去重方法

这种方法，确实还是自己的资历不够很多时候知道要干啥，但是我确实也写不出来

class Solution:
    def __init__(self):
        self.result = []
        self.path = []
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        used = [False]*len(candidates)
        self.backtracking(candidates,target,0,used)
        return self.result
    def backtracking(self,candidates,target,startindex,used):
        if sum(self.path[:])>target:
            return
        if sum(self.path[:])==target:
            self.result.append(self.path[:])
            return self.result
        for i in range(startindex,len(candidates)):
            if i>0 and candidates[i]==candidates[i-1] and used[i-1]==False:
                continue
            self.path.append(candidates[i])
            used[i] =True
            self.backtracking(candidates,target,i+1,used)
            self.path.pop()
            used[i] =False

2.3 本题小结

1. 这道题的关键点在于去重，对于python去重其实可以保证这个数比当前位置的值大，且与这个数值相等就好了
2. 这种used的去重方法，相对而言更适用于所有方法吧

3 leetcode131.分割回文串

题目链接：131. 分割回文串 - 力扣（LeetCode）

文章链接：代码随想录

视频链接：带你学透回溯算法-分割回文串（对应力扣题目：131.分割回文串）| 回溯法精讲！_哔哩哔哩_bilibili

思路：嗯，就是看不懂吧，，

3.1 视频后的思路

晚上看视频有点晕的感觉，就看讲解做了，嗯，觉得自己好懒多定义一个函数都不想，哈哈哈哈哈哈哈，其实定义一个新的函数就可以对其进行一个使用了

class Solution:
    def __init__(self):
        self.result = []
        self.path = []
    
    def partition(self, s: str) -> List[List[str]]:
        self.backtracking(s,0)
        return self.result

    def backtracking(self,s,startindex):
        if startindex==len(s):
            self.result.append(self.path[:])
            return
        for i in range(startindex,len(s)):
            if self.isPalindrom(s,startindex,i):
                self.path.append(s[startindex:i+1])
                self.backtracking(s,i+1)
                self.path.pop()

    def isPalindrom(self,s,left,right):
        while left<right:
            if s[left]!=s[right]:
                return False
            left +=1
            right-=1
        return True          

3.2 本题小结

1. 这道题，成功被自己的思维打败了，居然就是多定义一个函数并且在结尾处再对数据进行处理就好了
2. 晚上了，不知道写啥，但是觉得真的不难

4 今日小结

1. 第一道题是对之前题目的一个再回顾吧，我觉得剪枝没有太多的优化
2. 第二题当时困住我的地方是不知道如何去重，后来发现其实在python中去重的方法挺多的
3. 第三题，主要是真的不知道如何分割之类的问题，不过后来好好去思考了，跟着题目也算是可以做了吧