目录回溯算法理论基础回溯法定义回溯法的效率回溯法解决的问题回溯法模板77. 组合题目描述解题思路剪枝优化216. 组合总和 III题目描述解题思路剪枝优化17. 电话号码的字母组合题目描述解题思路回溯算法理论基础回溯法定义回溯法可以叫做回溯搜索法是一种搜索的方式回溯函数也是递归函数回溯法的效率回溯的本质是穷举穷举所有可能为了使回溯算法更加高效可以加剪枝的操作但是回溯的本质还是穷举适用于只能用暴力搜的问题回溯法解决的问题组合问题N个数里面按一定规则找出k个数的集合切割问题一个字符串按一定规则有几种切割方式子集问题一个N个数的集合里有多少符合条件的子集排列问题N个数按一定规则全排列有几种排列方式棋盘问题N皇后解数独等等回溯法模板回溯三部曲返回值以及参数backtracking返回值一般为void先写逻辑需要什么参数就填什么参数伪代码void backtracking(参数)终止条件参考树中搜到叶子节点就找到满足条件的一条答案存放该答案并结束本层递归if 终止条件:存放结果 return遍历过程回溯法是在集合中递归搜索集合的大小构成树的宽度递归的深度构成树的深度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,62向下就是3,4,5,6以此类推若k2那么[1,2],[1,3]就是一种结果若k3那么2继续向下延伸为3,4,5,63向下延伸为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,n1): self.comb.append(i) #组合问题的去重---comb中的去重比如说[1,4]和[4,1]是一种情况 self.backtracking(i1,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(i1,k,n,totali) self.path.pop()剪枝优化此题的剪枝优化除了对区间的优化之外还有如果totaln那么此时也可直接跳出#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(start1,digits) self.str.pop()