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

1 leetcode77. 组合

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

文章链接：代码随想录

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

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

1.1 回溯三部曲

回溯的方法

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

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.resultdef backtracking(self,n,k,startindex):if len(self.path)==k:self.result.append(self.path[:])return self.resultfor 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.resultdef backtracking(self,n,k,startindex):if len(self.path)==k:self.result.append(self.path[:])return self.resultfor 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 本题小结

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

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.resultdef backtracking(self,n,k,startindex):if len(self.path)==k and sum(self.path[:])==n:self.result.append(self.path[:])return self.resultfor i in range(startindex,10):self.path.append(i)self.backtracking(n,k,i+1)self.path.pop()

2.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.resultdef backtracking(self,n,k,sums,startindex):if sums>n:returnif len(self.path[:])==k and sums==n:self.result.append(self.path[:])return self.resultfor i in range(startindex,10-(k-len(self.path))+1):self.path.append(i)sums +=iself.backtracking(n,k,sums,i+1)sums -=iself.path.pop()

2.3 本题小结

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

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.resultself.backtracking(digits,0)return self.resultdef backtracking(self,digits,index):if index == len(digits):self.result.append(self.s)return self.resultdigit = 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]