代码随想录算法训练营第二十二天| leetcode77. 组合、leetcode216.组合总和III、leetcode17.电话号码的字母组合

1 leetcode77. 组合

题目链接：77. 组合 - 力扣（LeetCode）

文章链接：代码随想录

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

思路：开始想循环，感觉行不通，然后看了视频，就嗯理解了一些感觉跟递归的思路确实差不多

1.1 回溯三部曲

回溯的方法

1. 首先确定函数的参数和返回值
2. 确定终止条件
3. 确定单层递归的逻辑

1.2 视频后的思路

疑惑：为什么self.result.append(self.path[:])和这一句self.result.append(self.path)的结果不同，后面的输出居然是一个空的列表，有点不理解

class Solution:
    def __init__(self):
        self.result = []
        self.path = []
    def combine(self, n: int, k: int) -> List[List[int]]:
        self.backtracking(n,k,1)
        return self.result
    def backtracking(self,n,k,startindex):
        if len(self.path)==k:
            self.result.append(self.path[:])
            return self.result
        for i in range(startindex,n+1):
            self.path.append(i)
            self.backtracking(n,k,i+1)
            self.path.pop()

1.3 剪枝后的方法

文章链接：代码随想录

视频链接：带你学透回溯算法-组合问题的剪枝操作（对应力扣题目：77.组合）| 回溯法精讲！_哔哩哔哩_bilibili

错误点：这个在更改代码的时候，剪枝范围确定错误，导致报错了

class Solution:
    def __init__(self):
        self.result = []
        self.path = []
    def combine(self, n: int, k: int) -> List[List[int]]:
        self.backtracking(n,k,1)
        return self.result
    def backtracking(self,n,k,startindex):
        if len(self.path)==k:
            self.result.append(self.path[:])
            return self.result
        for i in range(startindex,n-(k-len(self.path))+2):
            self.path.append(i)
            self.backtracking(n,k,i+1)
            self.path.pop()

1.4 本题小结

1. 回溯算法感觉像是递归算法的一个升级版本，然后在写的时候其实和递归的非常像，其他的内容几乎没有变化
2. 在剪枝的过程需要手撕一下，确定剪枝的范围，第一次的时候就是将这个范围写的有问题，报错了

2 leetcode216.组合总和III

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

文章链接：代码随想录

视频链接：和组合问题有啥区别？回溯算法如何剪枝？| LeetCode：216.组合总和III_哔哩哔哩_bilibili

思路：跟上一个一样的，只是目前对剪枝不是很熟悉，不知道这道题应该如何进行剪枝的操作

2.1 自己的思路

感觉是可以进行剪枝的，但是目前学的不是很经典，不知道怎么剪枝

class Solution:
    def __init__(self):
        self.result = []
        self.path = []
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        self.backtracking(n,k,1)
        return self.result
    def backtracking(self,n,k,startindex):
        if len(self.path)==k and sum(self.path[:])==n:
            self.result.append(self.path[:])
            return self.result
        for i in range(startindex,10):
            self.path.append(i)
            self.backtracking(n,k,i+1)
            self.path.pop()

2.2 剪枝的方法

剪枝主要考虑两个位置：

1. 值不能超过他的目标值
2. 最后长度不够的问题

class Solution:
    def __init__(self):
        self.result = []
        self.path = []
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        self.backtracking(n,k,0,1)
        return self.result
    def backtracking(self,n,k,sums,startindex):
        if sums>n:
            return
        if len(self.path[:])==k and sums==n:
            self.result.append(self.path[:])
            return self.result
        for i in range(startindex,10-(k-len(self.path))+1):
            self.path.append(i)
            sums +=i
            self.backtracking(n,k,sums,i+1)
            sums -=i
            self.path.pop()

2.3 本题小结

1. 这道题目，精髓在于剪枝，但是我知道要做，不会做
2. 嗯，再一次一个人尝试去写，尝试成功啦

3 leetcode17.电话号码的字母组合

题目链接：17. 电话号码的字母组合 - 力扣（LeetCode）

文章链接：代码随想录

视频链接：还得用回溯算法！| LeetCode：17.电话号码的字母组合_哔哩哔哩_bilibili

思路：想到的是用ASCII码的值，然后转换，对应数值加几，递归里面有一点不知道怎么写

3.1 视频后的思路

似懂非懂，但是呢确实没想到用数组存储这个26个字母的问题

class Solution:
    def __init__(self):
        self.result = []
        self.result_list = ['','','abc','def','ghi','jkl','mno','pqrs','tuv','wxyz']
        self.s = str()
    def letterCombinations(self, digits: str) -> List[str]:
        if len(digits) == 0:
            return self.result
        self.backtracking(digits,0)
        return self.result
    def backtracking(self,digits,index):
        if index == len(digits):
            self.result.append(self.s)
            return self.result
        digit = int(digits[index])
        letters = self.result_list[digit]
        for i in range(len(letters)):
            self.s +=letters[i]
            self.backtracking(digits,index+1)
            self.s = self.s[:-1]    

3.2 本题小结

1. 就是有一种自己写代码的感觉，就是真的不难，但是我真的想不到，可以创建一个列表来进行数据读取，这个在之前有点没想到
2. 在列表切片的时候，可以直接到-1就代表最后一个不包含

4 今日小结

1. 怎么说呢，我感觉这种题上手还是有点儿感觉了，就是将递归嵌套的感觉
2. 第三题真的没想到需要将这个给建立一个列表来读取，哈哈哈哈哈哈，以后还是要加强技能