代码随想录算法训练营第二十二天|77、组合 216、组合总和III 17、电话号码的字母组合
目录
回溯算法理论基础
回溯法定义
回溯法的效率
回溯法解决的问题
回溯法模板
77. 组合
题目描述
解题思路
剪枝优化
216. 组合总和 III
题目描述
解题思路
剪枝优化
17. 电话号码的字母组合
题目描述
解题思路
回溯算法理论基础
回溯法定义
- 回溯法可以叫做回溯搜索法，是一种搜索的方式
- 回溯函数也是递归函数
回溯法的效率
- 回溯的本质是穷举，穷举所有可能，为了使回溯算法更加高效，可以加剪枝的操作，但是回溯的本质还是穷举
- 适用于只能用暴力搜的问题
回溯法解决的问题
- 组合问题：N个数里面按一定规则找出k个数的集合
- 切割问题：一个字符串按一定规则有几种切割方式
- 子集问题：一个N个数的集合里有多少符合条件的子集
- 排列问题：N个数按一定规则全排列，有几种排列方式
- 棋盘问题：N皇后，解数独等等
回溯法模板
- 回溯三部曲：
- 返回值以及参数：backtracking，返回值一般为void，先写逻辑，需要什么参数就填什么参数，伪代码
void backtracking(参数) - 终止条件：参考树中搜到叶子节点就找到满足条件的一条答案，存放该答案，并结束本层递归
if 终止条件:存放结果 return - 遍历过程：回溯法是在集合中递归搜索，集合的大小构成树的宽度，递归的深度构成树的深度
- 返回值以及参数：backtracking，返回值一般为void，先写逻辑，需要什么参数就填什么参数，伪代码
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) { 处理节点; backtracking(路径，选择列表); // 递归 回溯，撤销处理结果 }- for循环就是遍历集合区间，一个节点有多少个孩子，这个for循环就执行多少次
- for循环理解为横向遍历，backtracking就是纵向遍历
77. 组合
题目描述
给定两个整数
n和k，返回范围[1, n]中所有可能的k个数的组合。你可以按任何顺序返回答案。
解题思路
- 按照模板套题，首先回溯可以统一视为树型结构，for循环是集合中的所有元素相当于横向遍历，
backtracking是纵向延伸，把组合问题想象为一个树形结构，第一层都是集合中的所有元素，后面的就是根据第一层的每个元素进行延伸 - 例如集合[1,2,3,4,5,6],横向第一层为该集合，第二层1向下就是2,3,4,5,6，2向下就是3,4,5,6以此类推，若k=2那么[1,2],[1,3]就是一种结果；若k=3那么2继续向下延伸为3,4,5,6，3向下延伸为4,5,6，以此类推
- 由上述例子可以看出此时for循环就是横向扩展，第一层的和2下面延伸的都为扩展内容，k就表示向下延伸多少，代表了遍历回溯的过程
- 特别注意的是需要去掉前面的数字，此时就需要start来表示新扩展的起始位置
class Solution: def __init__(self): self.res = [] self.comb = [] def combine(self, n: int, k: int) -> List[List[int]]: self.backtracking(1,n,k) return self.res def backtracking(self,start,n,k): if len(self.comb) == k: #此时为comb[:]，若为comb[]则赋值为空 self.res.append(self.comb[:]) #终止当前递归 return for i in range(start,n+1): self.comb.append(i) #组合问题的去重--->comb中的去重，比如说[1,4]和[4,1]是一种情况 self.backtracking(i+1,n,k) self.comb.pop()剪枝优化
- 拿
[1,2,3,4]来举例，k = 3,目前选取的元素为len(self.comb) = 0，还需要选取的元素为k-len(self.comb),为什么要+1呢？如下图
#只需修改for循环 for i in range(start,n - (k - len(self.comb)+2) #for循环为左闭右开，故+2216. 组合总和 III
题目描述
找出所有相加之和为
n的k个数的组合，且满足下列条件：- 只使用数字1到9
- 每个数字最多使用一次
返回所有可能的有效组合的列表。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
解题思路
- 参考上一道题，区间由1~n变成了1~9，加了判断和是否为n的条件，那么就在回溯过程中顺便计算一下即可
class Solution: def combinationSum3(self, k: int, n: int) -> List[List[int]]: self.path = [] self.res = [] self.backtracking(1,k,n,0) return self.res def backtracking(self,start,k,n,total): if len(self.path) == k : if total == n: self.res.append(self.path[:]) return for i in range(start,9 - (k - len(self.path))+2): self.path.append(i) self.backtracking(i+1,k,n,total+i) self.path.pop()剪枝优化
- 此题的剪枝优化除了对区间的优化之外，还有如果
total>n，那么此时也可直接跳出
#backtracking函数 if total > n:return17. 电话号码的字母组合
题目描述
给定一个仅包含数字
2-9的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
解题思路
- 与前面两道题比对，最大的区别其实就是将前两题的数字转化为数组，而且已经把递归深处遍历的次数表明了，就是
len(digits)，每一层就是数字对应的字母，比如说23，第一层2对应abc，第二层3对应def，本质还是一样的 - 本题是多个集合求组和，前面两道题是集合中求组和，前者不需要start，因为是来自不同的集合，不需要单独对某个集合进行特殊处理
class Solution: def letterCombinations(self, digits: str) -> List[str]: self.str = [] self.res = [] #电话数字的映射 self.dict = {2:'abc',3:'def',4:'ghi',5:'jkl',6:'mno',7:'pqrs',8:'tuv',9:'wxyz'} #从下标索引0开始 self.backtracking(0,digits) return self.res def backtracking(self,start,digits): #两个都是同一种情况，当start超出digits或者长度到达其实本质还是当他们碰到叶子节点停止 # if start > len(digits) - 1: if len(self.str) == len(digits): #将数组转化为字符串，用''.join(数组)，而不是str(数组)，如果用str，则会变成["['a', 'd']"]，意思是将数组中每个元素转化为字符，而不是组合成字符串 self.res.append(''.join(self.str)) return #解析数字 nums = int(digits[start]) path = self.dict[nums] #横向 for c in path: self.str.append(c) #纵向延伸，延伸程度取决于digits大小 self.backtracking(start+1,digits) self.str.pop()