回溯

0 Basic 什么是回溯？ 回溯是在“解空间树”上做DFS，进入分支时选择，退出分支时撤销选择 模板：考虑 路径path: 已经做出的选择，如一个全局list 选择列表：当前层还能做的选择，如for loop范围 终止条件：长度/和等等 1def backtrack(path, 选择列表): 2 if 满足终止条件: 3 res.append(path[:]) # 注意拷贝 4 return 5 6 for 选择 in 选择列表: 7 if 不合法(选择): 8 continue / break # 剪枝 9 path.append(选择) # ① 做选择 10 backtrack(path, 新的选择列表) # ② 递归 11 path.pop() # ③ 撤销 收集时期：全节点收集 vs 叶子收集 1# 子集型：树上每个节点都是一个合法答案 2def dfs(start): 3 res.append(path[:]) # 写在开头，不 return 4 for i in range(start, n): 5 ... 6 7# 排列/定长组合：只有叶子是答案 8def dfs(): 9 if len(path) == n: 10 res.append(path[:]); return # 写在终止条件里 11 for i in range(n): 12 ... 复杂度估计：总时间 = 树的节点数 × 每个节点的处理代价 题 节点 / 叶子数 单节点代价 复杂度 78 子集 2ⁿ 个节点 拷贝 O(n) O(n · 2ⁿ) 46 全排列 n! 个叶子 拷贝 O(n) O(n · n!) 77 组合 C(n,k) 个叶子 O(k) O(k · C(n,k)) 22 括号生成 第 n 个卡特兰数 Cₙ O(n) O(n · Cₙ) 79 单词搜索 每步最多 3 个新方向 O(1) O(m·n·3^L) 51 N 皇后 ≤ n! O(n) O(n!) 经验：n ≤ 20 才敢直接写纯回溯（2²⁰ ≈ 10⁶）；排列型n ≤ 10（10! ≈ 3.6×10⁶）。数据范围超了，就该往 DP / 记忆化想 ...