算法与AI · 知识点深化 · 算法思想
回溯算法：排列、组合、子集、N 皇后的通用模板
回溯就是试错+撤销：一条路走到底，走不通退回来换一条。排列、组合、子集、N 皇后全是一个模板：递归向下→选择→递归→撤销选择。这一页把模板背熟，一类题通杀。
① 怎么学（4 步走，约 70 分钟）
先建立直觉再抠细节，按这四步走最稳：
1看图建立直觉（10 分钟）
读②③：先在脑子里画出本课核心结构图。
2记完整体系（15 分钟）
读④：把对比表和公式看懂，不要急着背。
3跟例题走一遍（20 分钟）
精读⑤：看三个例题怎么用知识点解题。
4刷题纠错（剩余时间）
做⑦⑩，错题回⑥诊断。
本课小目标学完你要能：① 写出回溯通用模板；② 区分排列/组合/子集；③ 去重；④ N 皇后思路。
② 一图看懂：回溯全景
读法：中心是本课主题，四条分支展开核心维度，下方是典型应用与高频易错点。
③ 本质直觉：回溯就是"走迷宫试错"
走迷宫：每条路走到头，死路退回来换一条。回溯一模一样：
模板三步：1. 做出选择（加入 path）；2. 递归往下；3. 撤销选择（pop）。
组合 vs 排列：组合不看顺序（1,2 和 2,1 一样），用 start 控制从哪开始选；排列看顺序，用 used 数组标记用过的。
剪枝：排序后跳过重复数字，避免重复解。
时间复杂度排列 O(n!)，组合 O(2^n)。别拿回溯解大数组题，那是 DP。
④ 完整知识体系
排列/组合/子集对比
| 类型 | 顺序 | start/used |
|---|
| 子集 | 不看顺序 | start | 排序后跳重复 |
| 组合 | 不看顺序 | start | 同上 |
| 排列 | 看顺序 | used 数组 | 排序后跳重复 |
| N皇后 | 棋盘 | 逐行放 | 列/对角线剪枝 |
通用模板dfs(start){ 收集; for(i=start..n){ 选择; dfs(i+1); 撤销 } }
去重if(i>start && nums[i]==nums[i-1]) continue;
为什么组合用 start
组合 [1,2] 和 [2,1] 重复。传 start 保证只往后选，不会回头。排列用 used 数组，每次从 0 开始但跳过用过的。
⑤ 应用场景与例题
例1 子集 [1,2,3]
每个元素选或不选，递归树 2^3=8 个。start 控制。
例2 全排列 [1,2,3]
used 标记。第一层选 1/2/3，剩下递归。共 6 个。
例3 组合总和 candidates=[2,3,5], target=8
可重复选同元素，dfs 传 i 而不是 i+1。剪枝：排序后超过 target break。
做题心法模板背熟：选择→递归→撤销，区别只在 start/used/剪枝。
⑥ 高频错误诊断（4 条）
错误1：递归后忘记 poppath 带着脏数据进入下一分支。
错误2：组合题用 used 不用 start产生重复排列。
错误3：去重条件写 i>0应该 i>start，同层跳过。
错误4：把回溯当 DP回溯是穷举，大数组会超时。
⑦ 考点真题演练（5 题）
考点分布
| 考法 | 出题形式 | 应对 |
|---|
| 模板 | 问核心三步 | 选择-递归-撤销 |
| 组合 | 问用 start 还是 used | start |
| 排列 | 问用什么 | used 数组 |
| 去重 | 问条件 | 同层跳重复 |
真题basic1. 回溯算法的核心三步是？
真题mid2. 组合问题用什么避免重复？
真题mid3. 排列问题用什么标记用过的元素？
真题hard4. 子集 [1,2,2] 去重，正确剪枝？
真题hard5. 回溯时间复杂度？
⑧ 必背知识点卡
模板：选->递归->撤销
组合：start 只往后
排列：used 标记
去重：i>start && 相等跳过
子集：每步收集当前 path
N皇后：逐行放，列/对角线剪枝
复杂：O(2^n) 别解大数组
⑨ 动手输出：写组合总和回溯
场景：candidates 找和为 target 的组合，可重复选。
① 排序：先排序方便剪枝。
② 递归：从 start 开始选。
③ 选择：加入 path，剩余 target-=cand。
④ 递归：传 i（可重复选当前）。
⑤ 撤销：pop，target 恢复。
口述思路组合可重复传 i，不可重复传 i+1。
⑩ 分层练习（基础 + 中档 + 拔高）
▍基础 6 题
基础6回溯时间复杂度？
O(2^n)/O(n!)。
▍中档 5 题
中档1为什么组合用 start？
避免 [1,2] [2,1] 重复。
中档2全排列为什么用 used？
排列看顺序，每元素用一次。
中档4N皇后怎么剪枝？
列和两条对角线不能有皇后。
中档5可重复选传 i 还是 i+1？
可重复传 i。
▍拔高 5 题
拔高1分割回文串怎么回溯？
枚举切割点，判断是否回文。
拔高3数独怎么解？
逐格尝试 1-9，校验行/列/宫。
拔高5组合总和 II 每个数用一次？
传 i+1。
⑪ 记忆口诀 + 7 天复习计划
三句口诀① 选择递归再撤销，模板背熟一类题。② 组合 start 排列 used，去重同层跳相等。③ N皇后逐行剪枝，指数复杂度别硬跑。
| 天 | 任务 | 自检 |
|---|
| 第 1 天 | 读②③，背通用模板 | 三步写对 |
| 第 2 天 | 背组合排列对比 + 基础 6 题 | 区别记住 |
| 第 3 天 | 做中档 5 题，写全排列 | 代码能跑 |
| 第 4 天 | 做拔高 5 题，写 N皇后 | 剪枝对 |
| 第 5 天 | 做⑦真题 5 题 | 限时每题 5 分钟 |
| 第 6-7 天 | 合书白板写模板 | 不看资料 |
← 返回算法与AI总览