回溯算法专题导读

回溯的本质：树形 DFS + 现场恢复

很多同学一听到"回溯"就发怵，其实把它拆开看非常朴素。回溯（Backtracking）的本质可以用一句话概括：在一棵隐式的搜索树上做深度优先遍历，走到死路就退回来，把刚才做的选择撤销掉，再换一条路走。

这里有两个关键词：

树形 DFS：所有回溯问题都能画成一棵 N 叉树，根节点是空解，每往下一层就多做一个选择；
现场恢复：递归返回前，必须把这一层做的选择"擦干净"，否则上一层会看到被污染的中间状态。

"做选择 → 递归 → 撤销选择"这三步是回溯的心跳，节奏永远是：

for 每个候选选择 in 当前层的选择列表:
    做出选择          // 修改路径、标记 used、推进起点
    递归进入下一层     // 深度 +1
    撤销选择          // 恢复路径、取消标记、回退起点

从代码组织方式看，回溯函数通常是无返回值、靠参数携带状态、靠成员变量收集结果的递归函数。它和普通的二叉树 DFS 最大的区别就是多了"撤销"这一步——因为路径/状态容器是跨层共享的，不撤销就会把本层的选择带到不该出现的分支里。

能解决哪五类问题

回溯解决的问题，本质上都是"穷举所有可能"。虽然题目千变万化，但归拢起来就五类：

类型	一句话考点	代表题目
组合	从 n 个元素里挑 k 个，讲顺序无关，靠 `startIndex` 防重复	77. 组合
切割	把字符串/序列切若干段，每段满足某条件，切线即选择	131. 分割回文串
子集	收集树上所有节点而非只收叶子，终止条件最宽松	78. 子集
排列	强调顺序，用 `used[]` 标记，每层都能从头选	46. 全排列
棋盘	二维网格上的选择 + 可行性校验，回溯思想不变	51. N 皇后

这五类是难度递进的：组合最简单（只有 startIndex），切割把"下标"当选择对象，子集改变收集时机，排列引入 used 数组，棋盘则是把前四类的技巧放到二维平面上综合运用。

通用模板框架

回溯有三个抽象概念，写题前先把它们想清楚，代码几乎是照着翻译：

路径（path）：已经做出的选择，即当前递归链上攒下来的部分解；
选择列表：当前层还有哪些候选可选（受 startIndex、used[]、剪枝条件约束）；
结束条件：什么时候 path 是一个合法答案，收进结果集并 return。

伪代码骨架：

backtracking(选择列表, 当前路径):
    if 满足结束条件:
        result.add(路径的拷贝)   // 注意必须深拷贝，不能直接 add 引用
        return
    for 选择 in 选择列表:
        剪枝: 若当前选择注定无解, 跳过
        做出选择
        backtracking(更新后的选择列表, 路径)
        撤销选择

对应的 Java 骨架，后续文章的每道题都是往这个骨架里填内容：

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    Deque<Integer> path = new ArrayDeque<>();
 
    public List<List<Integer>> combine(int n, int k) {
        backtracking(n, k, 1); // startIndex 从 1 开始
        return result;
    }
 
    private void backtracking(int n, int k, int startIndex) {
        // 结束条件：攒够了 k 个元素
        if (path.size() == k) {
            result.add(new ArrayList<>(path)); // 必须拷贝！
            return;
        }
        // 剪枝：i 最多到 n-(k-path.size())+1，后面元素不够凑齐 k 个
        for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) {
            path.addLast(i);              // 做选择
            backtracking(n, k, i + 1);    // 递归下一层，起点推进到 i+1
            path.removeLast();            // 撤销选择（回溯！）
        }
    }
}

一个容易忽略的细节：result.add(new ArrayList<>(path)) 必须拷贝。path 是共享容器，如果直接 add 引用，最后所有结果都会变成同一份（而且通常都是空列表，因为递归结束后 path 被清空）。

回溯 vs 多层嵌套循环

有同学会问：穷举为什么不用 for 循环写？当"每个解固定选 k 个元素"时，k 层嵌套 for 确实能穷举组合。但问题在于：

k 是变量。题目要求"任意长度的子集"，你不可能写任意层嵌套；
层数由递归深度决定，循环宽度由选择列表决定，二者天然正交。

回溯用一个递归函数 + 一个 for 循环，就把"k 层嵌套循环"压缩成了一层循环体：for 负责同一层的横向遍历，递归负责向下一层的纵向深入。以 n=3、k=2 的组合为例，搜索树长这样：

                []
        /       |       \
      [1]      [2]      [3]        ← 第一层 for 从 1 开始
     /   \      |
   [1,2] [1,3] [2,3]                ← 第二层 for 从上一层+1 开始
     ↓      ↓    ↓
   收集    收集  收集（叶子）

第一层 for 依次尝试 1、2、3；每选中一个，递归进入第二层 for（起点 +1）。递归返回后撤销选择，外层 for 接着试下一个数字——这就是"一个递归顶多层循环"的含义。遍历完整棵树的复杂度是 O(k × C(n,k))（每个解拷贝需要 O(k)），剪枝能显著减少实际访问的节点数。

题单地图总表

本专题的学习路线如下，建议按顺序刷，后面的题会反复用到前面的模板：

序号	题号	题目	归类	一句话考点
1	77	组合	组合	startIndex 引入与剪枝
2	216	组合总和 III	组合	组内去重天然满足，剪枝在元素和上
3	17	电话号码的字母组合	组合	多个集合间组合，不需要 startIndex
4	39	组合总和	组合	元素可重复选，递归传 i 而非 i+1
5	40	组合总和 II	组合	数组含重复元素，排序 + 树层去重
6	131	分割回文串	切割	切割线视角，判断回文
7	93	复原 IP 地址	切割	固定切 4 段 + 段合法性校验
8	78	子集	子集	收集所有节点，不只收叶子
9	90	子集 II	子集	有重复元素，排序 + 去重
10	491	递增子序列	子集	不能排序，用 set 做本层去重
11	46	全排列	排列	used[] 标记，每层从头选
12	47	全排列 II	排列	used 树枝去重 + 树层去重
13	51	N 皇后	棋盘	二维棋盘逐行放，列/对角线冲突校验
14	37	解数独	棋盘	二维递归，逐格填数

学习建议

先画树再写码：每道题动手前，手画搜索树的前三层，想清楚"这层 for 在选什么、什么时候收、下层从哪开始"，代码就是树的翻译。
抓住三要素做对比：做完一组题后，横向对比终止条件、收集时机、下一层起点三个要素的差异，模板感就出来了。
去重单独攻克：树层去重 vs 树枝去重是本专题最大的坑，放在第 3 篇用图专门讲透。

下一篇我们从最基础的组合问题（77. 组合）开始，把通用模板逐行拆开揉碎讲。

参考

代码随想录 · 回溯算法专题