【灵神高频面试题合集14-16】回溯（子集型、组合型、排列型）

基础算法精讲·题目汇总灵茶山艾府 - 【基础算法精讲】- GitHub视频灵茶山艾府的个人空间-灵茶山艾府个人主页-哔哩哔哩视频14 回溯 子集型 分割回文串课程讲解通过递归可以达到多重循环的效果增量构造答案的过程就是回溯的特点而这个过程就通常用递归实现对于递归参数中的 i它的含义不是第 i 个而是下标大于等于 i 的这部分这个过程就是在这棵树上做深度优先搜索dfs17. 电话号码的字母组合# 首先要把数字和要枚举的字母对应起来比如用一个数组下标2对应abc下标3对应def MAPPING [, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz] class Solution: def letterCombinations(self, digits: str) - List[str]: n len(digits) if n 0: return [] ans [] path [] * n # 路径是一个长度为n的数组 def dfs(i): if i n: ans.append(.join(path)) # 把数组转换成字符串 return # 对于非边界条件需要枚举第i个数字对应的字母是什么 for c in MAPPING[int(digits[i])]: path[i] c dfs(i1) dfs(0) # 递归入口就是从第0个字符开始枚举 return ans时间复杂度对于回溯的问题也可以从循环的角度来理解。枚举第一个字母就是最外层的循环、第二个字母就是第二层循环以此类推。一共最多需要循环 4^n 次一个数字最多对应4个字母最后生成答案这里需要花费 O(n) 的时间。因此时间复杂度就是 O(n * 4^n)空间复杂度O(n)78. 子集0-1背包问题也可以算一种子集型回溯每个元素都可以选/不选子集型回溯的两种代码模板思路1非边界条件不选的话这个数直接跳过递归到 i1选的话先把它加到路径中然后递归再恢复现场边界条件把路径中记录的答案加到 ans 中。注意由于 path 是全局变量会发生变化所以要固定下来即 copy()class Solution: def subsets(self, nums: List[int]) - List[List[int]]: ans [] path [] n len(nums) def dfs(i): if i n: ans.append(path.copy()) return dfs(i1) # 不选 # 选 path.append(nums[i]) dfs(i1) path.pop() dfs(0) return ans时间复杂度每次递归只有不选和选两种情况所以一共会递归 2^n 次。再加上 copy 的时间是 O(n) 的所以时间复杂度是 O(n * 2^n)空间复杂度O(n)思路2class Solution: def subsets(self, nums: list[int]) - list[list[int]]: ans [] path [] n len(nums) def dfs(i): ans.append(path.copy()) if i n: return for j in range(i, n): path.append(nums[j]) dfs(j1) path.pop() dfs(0) return ans131. 分割回文串class Solution: def partition(self, s: str) - list[list[str]]: ans [] path [] n len(s) def dfs(i): if i n: ans.append(path.copy()) return for j in range(i, n): t s[i: j1] if t t[::-1]: path.append(t) dfs(j1) path.pop() dfs(0) return ans时间复杂度每次递归只有不选和选两种情况所以一共会递归 2^n 次。再加上 copy 的时间是 O(n) 的所以时间复杂度是 O(n * 2^n)空间复杂度O(n)课后作业257. 二叉树的所有路径113. 路径总和 II784. 字母大小写全排列LCP 51. 烹饪料理2397. 被列覆盖的最多行数1239. 串联字符串的最大长度2212. 射箭比赛中的最大得分2698. 求一个整数的惩罚数93. 复原 IP 地址15 回溯 组合型 剪枝课程讲解77. 组合class Solution: def combine(self, n: int, k: int) - list[list[int]]: ans [] path [] def dfs(i): d k - len(path) if i d: # 剪枝 return if len(path) k: ans.append(path.copy()) return for j in range(i, 0, -1): path.append(j) dfs(j-1) path.pop() dfs(n) return ans时间复杂度叶子的个数 × 从根到叶子的路径长度。对于本题就是 O(k × C(n, k))空间复杂度O(k)216. 组合总和 IIIclass Solution: def combinationSum3(self, k: int, n: int) - List[List[int]]: ans [] path [] def dfs(i, t): d k - len(path) # 剪枝 if t 0 or t (i i-d1) * d // 2: return if len(path) k: ans.append(path.copy()) return for j in range(i, d-1, -1): path.append(j) dfs(j-1, t-j) path.pop() dfs(9, n) # 从9倒着选需要求得和是n return ans时间复杂度O(k × C(9, k))空间复杂度O(k)22. 括号生成class Solution: def generateParenthesis(self, n: int) - list[str]: m 2 * n ans [] path [] * m def dfs(i, open): # open是左括号的数量 if i m: ans.append(.join(path)) return if open n: # 还能选左括号 path[i] ( dfs(i1, open1) if i-open open: # 右括号个数 左括号 path[i] ) dfs(i1, open) dfs(0, 0) return ans时间复杂度组合问题。O(n * C(2n, n))。由于左右括号之间是有约束的实际递归次数没有这么多卡特兰数空间复杂度O(n)课后作业39. 组合总和93. 复原 IP 地址16 回溯 排列型 N皇后课程讲解46. 全排列数组元素各不相同全排列的个数就是数组长度的阶乘写法1class Solution: def permute(self, nums: list[int]) - list[list[int]]: n len(nums) ans [] path [0] * n def dfs(i, s): # i表示需要构造大于等于i的排列s表示剩余还可以选的数的集合 if i n: ans.append(path.copy()) return for x in s: # 从s里枚举还没有选的数 path[i] x dfs(i1, s-{x}) dfs(0, set(nums)) # 初始化 return ans时间复杂度O(n * n!)有 n! 个叶子路径长度是 n。节点个数的精确值为 e * n! 向下取整空间复杂度O(n)写法2class Solution: def permute(self, nums: list[int]) - list[list[int]]: n len(nums) ans [] path [0] * n on_path [False] * n # 布尔数组用来标记每个下标是否选择了 def dfs(i): # i表示需要构造大于等于i的排列 if i n: ans.append(path.copy()) return for j in range(n): if on_path[j] False: path[i] nums[j] on_path[j] True dfs(i1) on_path[j] False # 恢复现场 dfs(0) return ans时空间复杂度一样51. N 皇后写法1class Solution: def solveNQueens(self, n: int) - list[list[str]]: ans [] col [0] * n def valid(r, c): # r表示当前枚举的是第r行 for R in range(r): C col[R] if rc RC or r-c R-C: return False return True def dfs(r, s): # r表示当前要枚举的行号s表示剩余可以枚举的列号 if r n: ans.append([.*c Q .*(n-1-c) for c in col]) return for c in s: # 从s中枚举剩余没有选的列号 if valid(r, c): col[r] c # 放皇后 dfs(r1, s-{c}) dfs(0, set(range(n))) return ans时间复杂度O(n^2 * n!)其中 n^2 是生成答案的时间n! 是枚举全排列的时间空间复杂度O(n)写法2判断当前位置能不能放皇后从 O(n) 优化到 O(1)class Solution: def solveNQueens(self, n: int) - list[list[str]]: ans [] col [0] * n on_path [False] * n m 2*n - 1 diag1 [False] * m diag2 [False] * m def dfs(r): # r表示当前要枚举的行号 if r n: ans.append([.*c Q .*(n-1-c) for c in col]) return for c in range(n): if not on_path[c] and not diag1[rc] and not diag2[r-c]: col[r] c on_path[c] diag1[rc] diag2[r-c] True dfs(r1) on_path[c] diag1[rc] diag2[r-c] False dfs(0) return ans课后作业52. N 皇后 II357. 统计各位数字都不同的数字个数2850. 将石头分散到网格图的最少移动次数