代码随想录 Day22 | 回溯算法-part01（77. 组合、216.组合总和III、17.电话号码的字母组合）

今日总结回溯和组合问题、剪枝题目77. 组合题目链接题目题解第一想法自己实现class Solution: def combine(self, n: int, k: int) - List[List[int]]: # 回溯,用一个path数组存储路径 res [] def dfs(i,path): if len(path) k: res.append(path.copy()) return for j in range(i1,n1): # 从i1开始 path.append(j) dfs(j,path) path.pop() return dfs(0,[]) return res时间复杂度O(k*C(n,k))空间复杂度O(k*C(n,k))算结果学习题解剪枝优化当剩余可选的数字个数少于还需选取的个数时继续搜索无法构成有效组合因此提前终止循环。class Solution: def combine(self, n: int, k: int) - List[List[int]]: # 回溯,用一个path数组存储路径 res [] def dfs(i,path): if len(path) k: res.append(path.copy()) return # 剪枝优化 for j in range(i1, n - (k - len(path)) 2): # 从i1开始 path.append(j) dfs(j,path) path.pop() return dfs(0,[]) return res可以从深度优先遍历树的角度理解剪枝和回溯。216.组合总和III题目链接题目题解第一想法回溯path存储路径,sumn累加和自己实现class Solution: def combinationSum3(self, k: int, n: int) - List[List[int]]: # 回溯path存储路径,sum累加和 res [] def dfs(i,path,sumn): if sumn n and len(path) k: res.append(path.copy()) return if sumn n: return # 当10 - j (k - len(path)) 即 j 10 - (k - len(path)) 时剪枝 for j in range(i1,11 - (k - len(path))): path.append(j) sumn j dfs(j,path,sumn) sumn - j path.pop() return dfs(0,[],0) return res时间复杂度O(k⋅C(9,k))空间复杂度O(k⋅C(9,k))学习题解两种角度理解选或不选以及选哪个选哪个组合生成剪枝每次从大于上一个数字的剩余数字中依次选择一个递归构造组合并用剩余数字个数和总和进行剪枝。选或不选组合枚举对每个数字1~9递归地考虑“选”或“不选”两条分支并用当前已选个数和总和进行剪枝。class Solution: def combinationSum3(self, k: int, n: int) - List[List[int]]: res [] # i: 当前考虑的数字 1~9 def dfs(i, path, sumn): if len(path) k and sumn n: res.append(path.copy()) return if i 9 or len(path) k or sumn n: return # 不选当前数字 dfs(i 1, path, sumn) # 选当前数字 path.append(i) dfs(i 1, path, sumn i) path.pop() dfs(1, [], 0) return res17.电话号码的字母组合题目链接题目题解第一想法回溯对digits中的每个数字枚举选哪个字母。自己实现class Solution: def letterCombinations(self, digits: str) - List[str]: # 回溯对digits中的每个数字枚举选哪个字母 res [] n len(digits) mp [,,abc,def,ghi,jkl,mno,pqrs,tuv,wxyz] def dfs(i,s): if i n: res.append(s[:]) return for c in mp[int(digits[i])]: s c dfs(i1,s) s s[:-1] return dfs(0,) return res时间复杂度O(3m⋅4n)空间复杂度O(3m⋅4n)学习题解可以用数组存储然后加入res时用.join(path)。path可以用全局变量不用每次传入。如果digits为空可以提前返回空数组。也可以用BFS法逐层生成。今日收获组合问题通用模板递归中循环从起始索引开始路径满足长度时收集结果并利用剩余可选数进行剪枝。组合总和 III通过和与个数双重剪枝也可采用“选或不选”的视角。电话号码组合建立数字到字母的映射递归遍历每个数字对应的字母注意空字符串提前返回。学习时长1.5 小时模板77. 组合剪枝版def combine(self, n: int, k: int) - List[List[int]]: res [] def dfs(start, path): if len(path) k: res.append(path.copy()) return # 剪枝剩余数字个数 还需要选的个数 for i in range(start, n - (k - len(path)) 2): path.append(i) dfs(i 1, path) path.pop() dfs(1, []) return res216. 组合总和 III组合生成剪枝def combinationSum3(self, k: int, n: int) - List[List[int]]: res [] def dfs(start, path, cur_sum): if len(path) k and cur_sum n: res.append(path.copy()) return if cur_sum n or len(path) k: return # 剪枝剩余数字最多到 9且保证足够个数 for i in range(start, 10 - (k - len(path)) 1): path.append(i) dfs(i 1, path, cur_sum i) path.pop() dfs(1, [], 0) return res17. 电话号码的字母组合def letterCombinations(self, digits: str) - List[str]: if not digits: return [] mp [,,abc,def,ghi,jkl,mno,pqrs,tuv,wxyz] res [] def dfs(i, s): if i len(digits): res.append(s) return for c in mp[int(digits[i])]: dfs(i 1, s c) dfs(0, ) return res易错点77 题剪枝时n - (k - len(path)) 1容易算错注意range(start, end1)需包含end。216 题剪枝范围10 - (k - len(path))要保证最大能取到 9正确写法range(start, 10 - (k - len(path)) 1)。递归终止时同时判断len(path)k和cur_sumn缺少任一都会出错。17 题若digits为空字符串应直接返回[]否则会得到[]。数字 1 对应空字符串需在映射中留空并跳过或直接处理。递归中字符串拼接会产生新对象不影响回溯也可以使用path列表 .join。