回溯
01 / 一句话本质
深度优先地探索一棵决策树,在回溯时撤销每一次选择 — 于是同一个数组、同一个递归栈帧、同一条路径轮流构造出每个候选解。
题目枚举一个集合的所有子集输入[1, 2, 3]2ⁿ8
已输出—— 还没有 ——
从根节点开始,当前子集为 [ ]。对每个元素决定:纳入或排除。
步
0 / 15
深度
0
当前子集
[ ]
已输出
0
0 / 15
02 / 模式骨架
# 在决策树上做 DFSbacktrack(state, depth):if 到达叶子或被剪枝:记录 / 丢弃;returnfor 当前深度的每个 choice:// 1. 扩展状态将 choice 应用到 statebacktrack(state, depth + 1)// 2. 在尝试下一个兄弟之前撤销从 state 中撤销 choice
03 / 什么时候用这个模式
"所有 / 每一种"
你需要枚举所有合法配置,而不是找出某一个最优答案。 问题关心的是完备性。
"构造一个序列"
答案是一连串决策 —— 选元素、选行、选字符 —— 且这些决策彼此牵连。
"满足某个约束"
每个部分状态都可以增量校验 —— 一旦约束已破坏,就能剪掉整棵子树。
"阶乘 / 指数级"
题面说搜索空间巨大,但约束让其中大部分不可达 —— 剪枝才是让它在实际中可行的关键。
04 / 常见坑
i.
忘记在尝试下一个兄弟前撤销选择。
回溯里的"回"是最容易遗漏的部分。递归返回后若
state 没有恢复, 脏状态就会被带进兄弟分支 —— 产出错误子集、重复解,或非法棋盘。ii.
在叶子处保存引用而不是拷贝。
记录结果时,push 的应该是当前状态的
copy,而不是引用本身。 后续递归还会继续修改这份状态,你收集的答案也会被一起改写。iii.
漏掉提前剪枝的判断。
朴素版本会遍历整棵树 —— 指数级。快的版本在下钻之前就检查部分状态是否还可能导出合法解,不行就跳过整棵子树。 对大多数问题而言,剪枝是"能跑"和"跑不动"的分水岭。
05 / 去 LeetCode 上练习
四道题,按分支宽度排序。Subsets 就是上面的那棵二叉树;其余题分支更宽,需要靠剪枝维持速度。