回溯算法
回溯算法（Backtracking）是一种系统地搜索所有候选解的通用算法范式——本质是「在解空间树上做深度优先搜索（DFS）+ 失败时撤销选择回退上一层」。它把一个复杂的求解问题抽象成一棵「解空间树」（每层代表一次选择，每条从根到叶的路径代表一个候选解），然后从根出发逐层「选 → 探索 → 撤销」：在当前节点尝试所有合法的分支往下走，一旦走到死路（不满足约束或已无选择）就撤销上一步选择回到父节点，换另一条分支继续。它是有组织的暴力枚举——比朴素嵌套循环强在「剪枝」：在搜索过程中提前判断某分支不可能产生合法解，直接整棵子树剪掉不再递归，从而把指数级的搜索空间大幅压缩。
回溯是组合优化类问题的万能解法，几乎所有「求所有解 / 所有方案」的问题都能套：①排列/组合/子集三大经典（用 used 数组或 start 索引控制分支）；②约束满足问题（CSP）如 N 皇后、数独、图着色（边走边检查约束剪枝）；③网格搜索如单词搜索（DFS + 回溯标记已访问格子）；④分割问题如回文分割、IP 还原。回溯与动态规划（DP）常被混淆——回溯求「所有解」、DP 求「最优解/方案计数」：当只需要最优值时 DP 用记忆化/状态转移把指数搜索降到多项式；当需要枚举出每个具体方案时回溯不可替代（DP 只给值不给方案）。掌握回溯的关键就三步：识别解空间结构（子集树/排列树）→ 套用「选/递归/撤销」模板 → 设计剪枝条件剪掉无解分支。
评价
优点
- 万能性：只要能把问题建模成「逐步做选择 + 判断合法性」的形式，几乎都能用回溯求解——是组合搜索类问题的「瑞士军刀」。
- 思路直观、模板统一：核心就「选 → 递归 → 撤销」三步，全排列/组合/子集/N 皇后/数独共用同一套模板，只是分支选择方式和剪枝条件不同。
- 支持剪枝：通过提前判断约束、排序后跳过、可行性预估等手段，能在指数级解空间中大幅剪掉无解子树，实战中往往远快于理论上界。
- 能输出所有具体方案：动态规划只能给出最优值或方案数，回溯能逐一列举出每个合法解——这是它在「枚举类」问题上不可替代的原因。
缺点
- 指数级复杂度：解空间树节点数通常为 O(2ⁿ) 或 O(n!)，规模稍大就爆炸（如 N 皇后 N>20 基本无解，全排列 n>12 已很慢）——只能求解中小规模问题。
- 不擅长求最优值/计数：若只求「最优解」或「方案总数」，回溯会重复子问题，远不如动态规划高效（DP 用记忆化把指数级降到多项式级）。
- 剪枝依赖经验：通用模板能跑但慢，能否剪得干净、剪得正确高度依赖问题本身和设计经验，写错剪枝条件还会漏解。
- 空间栈深：递归深度等于解空间树高度（最坏 O(n)），N 很大时可能栈溢出，需改迭代或手动模拟栈。
本叶地图
- 入门 —— 回溯=DFS+撤销选择、解空间树（子集树/排列树）、回溯三步（选择/递归/撤销）、与暴力枚举的关系、回溯 vs DP
- 回溯框架与剪枝优化 —— 通用回溯模板、全排列/组合/子集三模板区别（used 数组 vs start 索引）、剪枝策略、代码实战
- 经典回溯问题 —— N 皇后、数独求解、单词搜索、回文分割、组合总和、剪枝实战
- 参考 —— 回溯通用模板、排列/组合/子集/N 皇后/数独模板速查、剪枝技巧、复杂度、易错点
交互演示
- N 皇后可视化演示 —— 逐行放置、列与对角线冲突检查、剪枝回退
- 子集可视化演示 —— 子集树上的「选/不选」二叉搜索
- 全排列可视化演示 —— 排列树上的 used 数组分支控制
- 数独可视化演示 —— 约束满足问题上的回溯求解