回溯与剪枝：解空间搜索

一句话定义

回溯（Backtracking）是在「决策树」上做深度优先搜索的系统性枚举：每层做一个选择，递归进入下一层，返回前撤销选择恢复现场；剪枝（Pruning）则在展开前用约束/最优性判定整棵子树跳过，把指数空间砍到可跑。

为什么重要

「求所有解」「求一个满足约束的解」「数独/N 皇后这类无好结构的硬题」没有 DP 式的多项式通路，回溯是通用解法；排列/组合/子集三大模板覆盖了一半以上的搜索题。剪枝思维（先判不可行再下探）也是约束满足、SAT 求解器等工业搜索的微观版本。

前置知识

kp-008（栈/DFS 机制）；kp-016（DFS 遍历——回溯是其带状态恢复的版本）；kp-011（决策树视角）。

核心概念

• 三要素：路径（已做选择）、选择列表（当前可选项）、结束条件；框架 = 做 → 递归 → 撤销。
• 三大模板：排列（全排列，用 used 数组去重位置）、组合（起点 start 防重复组合）、子集（每个节点都收集一次）。
• 去重：同层跳过重复元素——先排序，若 i > start 且 a[i] == a[i−1] 则跳过，保证「同一位置不重复选等值元素」。
• 两类剪枝：可行性剪枝（约束已破坏：列冲突、和超界）与最优性剪枝（当前已劣于已知最优：界/下界估计）。
• 复杂度：排列 n!、子集 2ⁿ、组合 C(n,k)——指数是本质，剪枝只改常数与实际分支数，不改变最坏阶。

直观类比

回溯像走迷宫并在每个岔口做记号：此路不通就退回上一个岔口（撤销选择）换条路；剪枝则是望一眼发现前面是死墙，连走都不走。决策树上每个节点是「一次部分选择」，叶子是完整方案。

原理与机制

全排列模板（含去重版要点）：

函数 dfs(path, used):
    若 path 长度 == n: 收集 path ; 返回
    对于 i ∈ 0..n−1:
        若 used[i]: 跳过
        若 i > 0 且 a[i] == a[i−1] 且 未used[i−1]: 跳过   // 同层去重
        used[i] ← true ; path.push(a[i])
        dfs(path, used)
        path.pop() ; used[i] ← false        // 撤销，恢复现场

八皇后剪枝：按行放置，只需三个布尔集合记录列、主对角线、副对角线占用；冲突 O(1) 判定即「可行性剪枝」，把 8⁸≈1677 万的盲搜砍到约 2057 个叶解、搜索节点数万级。位运算版（kp-031）用 (avail & −avail) 枚举可用列更快。

图示

子集 {1,2,3} 的决策树（每个节点都是一个子集）:
                 {}
          ┌────────┼────────┐
         {1}      {2}      {3}
        ┌─┴─┐     │        │
      {1,2} {1,3} {2,3}    —
        │
      {1,2,3}
DFS 路径: 根 → {1} → {1,2} → {1,2,3} → 回溯 → {1,3} → 回溯 → {2} …
八皇后: 行为层，列为选择，列/对角冲突 → 剪枝 ✂

实例或案例

• 全排列（LeetCode 46/47 含去重）、子集（78/90）、组合总和（39/40）：三大模板直接命中。
• N 皇后（51/52）：可行性剪枝 + 对角编码；N=15 以上需位运算加速。
• 数独求解器（37）：候选最少的格子优先（MRV 启发式，本质是动态剪枝顺序）。
• 单词搜索（79）与图上的路径枚举：回溯 + 网格 visited 恢复。

常见误区

• 忘记撤销选择（或撤销不完整）：状态污染，后续分支在脏状态上搜索，结果既错又慢。
• 去重条件写错（漏排序、条件里用 used[i−1] 方向搞反）：产生重复解或漏解；「先排序再同层跳过」是标准姿势。
• 用回溯去解「最优值」却不带界剪枝：裸枚举在 n>20 即不可行，应加最优性剪枝或转 DP。
• 混淆「求所有解（回溯）」与「求最优值（DP/贪心优先）」：场景选错则复杂度爆炸。

自测题

1. 写出子集模板的伪代码，说明它与组合模板的差异。

答案要点：子集在每个节点都收集、循环从 start 起；组合仅在叶子（长度达 k）收集，其余同构。

1. 排列去重条件为什么是 a[i]==a[i−1] && !used[i−1]？

答案要点：保证等值元素只按「从左到右首次可用」的顺序被同层选取；若 used[i−1] 为真说明是同一分支的深层，不在同层。

1. 估计八皇后剪枝前后的搜索量级。

答案要点：无剪枝 8⁸ ≈ 1.7×10⁷ 叶；加三集合剪枝后访问节点降至数万，实际解 92 个——数量级差约 10³。

与其他知识点的关系

kp-016 的 DFS 是「图上找可达」而回溯是「决策树上找方案」，机制同源、语义不同；kp-026 DP 常是回溯「只求最优值」时的多项式替代；kp-031 位运算是剪枝的加速器；kp-019 增广路径的迭代改进与回溯的「换条路」精神相通。

延伸阅读

Skiena《算法设计指南》回溯章节（含 MRV 启发式）；《算法竞赛入门经典》第 7 章（暴力求解与剪枝）。