开始前应具备
- 掌握递归与调用栈
- 理解树的 DFS
- 能够区分路径状态和最终答案
CHAPTER 08 · 暴力搜索
回溯与组合搜索
把选择过程画成决策树，用选择、递归、撤销覆盖所有可能。
3 个知识小节6 道分层练习5–6 天 建议周期
00
BEFORE LEARNING
先理解为什么学
回溯是有组织的暴力枚举。关键不是递归本身，而是把选择过程画成决策树，并确保每条路径只被访问一次。
完成本章后
- 写出通用回溯骨架
- 区分排列、组合与子集
- 使用剪枝减少无效分支
01
CORE LESSONS
知识讲义
01
LESSON
选择、递归、撤销
什么时候想到它？
需要枚举所有合法方案、路径或组合，而且每一步都从若干选择中决定下一步。
路径保存已经做出的选择，选择列表给出当前可选项，结束条件决定何时收集答案。递归返回后撤销选择，让同层其他分支从相同状态开始。
推导步骤
- 定义路径和结束条件
- 枚举当前层所有选择
- 做选择并更新状态
- 递归后撤销选择
思维模板 / 伪代码
def backtrack(path, choices):
if finished(path): collect(path); return
for choice in choices:
make(choice)
backtrack(path, next_choices)
undo(choice)02
LESSON
子集、组合与排列
什么时候想到它？
子集关心选或不选，组合不关心顺序，排列关心顺序。三者主要区别在下一层选择范围。
组合和子集使用 start 控制只能向后选择，从结构上避免重复；排列每层都可选择未使用元素，因此需要 used 数组。
推导步骤
- 先判断答案是否区分顺序
- 组合使用 start_index
- 排列使用 used 标记
- 输入含重复值时排序并进行同层去重
思维模板 / 伪代码
# 组合
for i in range(start, n):
path.append(a[i])
backtrack(i + 1)
path.pop()03
LESSON
约束剪枝与网格回溯
什么时候想到它？
部分路径已经违反约束，或在网格中寻找不能重复使用格子的路径。
剪枝是在进入更深递归前排除必然失败的分支。网格搜索还需要标记当前路径已使用的格子，并在返回时恢复，允许其他起点重新使用。
推导步骤
- 把约束写成可提前判断的条件
- 进入格子时标记当前路径
- 匹配失败立即返回
- 离开格子时恢复现场
思维模板 / 伪代码
if invalid(state): return
mark(choice)
for next in candidates: backtrack(next)
unmark(choice)02
READING
延伸阅读
先读完本站讲义并尝试练习；遇到推导不清的地方，再回到原始教程深入阅读。
03
PRACTICE LADDER
按作用分层练习
题量由知识点决定，不再固定为 5 道。先完成“入门”和“模板”，再做变式与综合；挑战题可以留到复习阶段。
入门认识结构模板独立复现变式迁移条件综合组合技巧挑战延后突破
选择、递归、撤销
1 道 · 依次完成
LC 78入门中等
子集
Subsets
为什么选：每个元素选或不选，观察完整决策树。
子集、组合与排列
3 道 · 依次完成
LC 77模板中等
组合
Combinations
为什么选：用 start 避免组合重复。
LC 46变式中等
全排列
Permutations
为什么选：排列每层选择未使用元素，需要 used 状态。
LC 39综合中等
组合总和
Combination Sum
为什么选：元素可重复选择，下一层 start 不加一。
约束剪枝与网格回溯
2 道 · 依次完成
LC 22变式中等
括号生成
Generate Parentheses
为什么选：通过左右括号数量提前剪掉非法前缀。
LC 79挑战中等
单词搜索
Word Search
为什么选：在网格路径中完成选择、标记、递归和恢复。
04
PERSONAL NOTEBOOK
我的学习笔记
我如何识别这个模式？今天卡在哪里？下次需要先检查什么？
笔记保存在当前浏览器