什么是回溯算法？回溯的框架（模板）和三要素是什么？

简化版

回溯就是在一棵「决策树」上做深度优先搜索：每一步做一个选择、递归往下探，探到底或此路不通就撤销刚才的选择、回到上一步换一个选择继续。三要素是路径（已经做过的选择）、选择列表（当前还能做的选择）、结束条件（到达叶子或满足目标）。核心动作永远是「做选择 → 递归 → 撤销选择（回溯）」。它本质是暴力穷举，靠剪枝砍掉不可能的分支来提速。

详细版

通用模板（几乎所有回溯题都套它）：

List<解> res = new ArrayList<>();

void backtrack(路径, 选择列表) {
    if (满足结束条件) {
        res.add(new ArrayList<>(路径)); // 收集一个解，注意要拷贝一份
        return;
    }
    for (选择 : 选择列表) {
        if (该选择不合法) continue;     // 剪枝：提前跳过

        路径.add(选择);                 // ① 做选择
        backtrack(路径, 新的选择列表);   // ② 递归进入下一层
        路径.removeLast();              // ③ 撤销选择（回溯）
    }
}

三要素：

路径：已经做出的选择序列（path）。
选择列表：当前这一步可以做的选择（常用 start 下标或 used[] 数组界定）。
结束条件：走到决策树底层、无法再选，或满足题目要求，此时收集解。

三个关键点：

收集解时要 new 一份拷贝——path 是全程共享、不断被修改的可变对象，直接存引用会被后续操作改掉。
「做选择」和「撤销选择」必须成对、对称，撤销要精确还原到做选择之前的状态。
剪枝决定效率：越早排除不可能的分支，省的时间越多。

完整版教学

一、回溯的本质：决策树上的 DFS

理解回溯，先在脑子里画出一棵决策树：树的每个节点代表「已经做了一部分选择」的中间状态，从一个节点往下的每条边代表「再做一个选择」。

回溯做的事，就是从根开始，深度优先地遍历这棵决策树：沿一条路一直往下走（不停做选择），走到叶子（一个完整的解）或走不通（被剪枝）时，退回上一个岔路口，换一条没走过的边继续。这个「退回去换一条」的动作就是「回溯」。

所以回溯 = 穷举决策树的所有路径，只不过用「撤销选择」优雅地复用同一份路径变量，而不是每条路都从头拷贝。

二、三要素：路径、选择列表、结束条件

任何一道回溯题，动手前先想清楚这三样：

路径（已做的选择）：从根走到当前节点，一路做了哪些选择。通常用一个 List path 维护。
选择列表（当前能做的选择）：站在当前节点，还能往哪些方向走。这是最需要动脑的地方——
- 排列问题：用 boolean[] used 标记哪些元素已在路径里，没用过的都能选；
- 组合/子集问题：用一个 start 下标，只能选 start 及之后的元素（避免选出顺序不同的重复组合）。
结束条件：什么时候到达一个解。比如「路径长度等于 n」（排列）、「剩余目标为 0」（组合总和）、「遍历到字符串末尾」（切割）。

三、通用模板（建议背下来）

模板的骨架是「判断结束 → 遍历选择 → 做选择、递归、撤销」（见详细版代码）。把它背熟后，做题只需往三个空里填内容：

结束条件是什么？
选择列表怎么界定（start 还是 used）？
有没有可以剪枝的地方？

绝大多数回溯题（全排列、子集、组合总和、N 皇后、括号生成、分割回文……）都是这套模板换皮。

四、核心：做选择与撤销选择必须对称

回溯之所以能用一份共享的 path 跑遍整棵树，靠的是每次递归返回后，把状态精确还原：

path.add(x);          // 做选择：状态从 A 变到 B
backtrack(...);       // 在状态 B 下把子树全跑完
path.removeLast();    // 撤销选择：把状态从 B 还原回 A

如果做了选择却忘了撤销，或撤销得不干净（比如还改了别的标记数组却没恢复），后面的分支就会在被污染的状态上搜索，结果全错。凡是进入递归前改动过的东西（path、used[]、棋盘格子……），递归返回后都要一一还原。 这是回溯最容易出 bug 的地方。

五、剪枝：回溯效率的关键

回溯本质是穷举，最坏是指数级。剪枝就是在决策树上提前砍掉「一看就不可能产生解」的整棵子树，是回溯优化的主要手段：

合法性剪枝：这个选择会违反约束就直接跳过（如 N 皇后中该列/对角线已有皇后）。
可行性剪枝：当前部分解已经不可能达成目标就返回（如组合总和里，排序后 候选 > 剩余目标 就 break，因为后面更大）。
去重剪枝：含重复元素时，跳过会产生重复解的选择（先排序，再 if (nums[i]==nums[i-1] && !used[i-1]) continue）。

剪枝不改变「穷举」的正确性，只是不去走注定失败的路。剪得越早、越狠，越快。

六、回溯 vs DFS vs 递归

三者关系常被问：

递归是一种实现手段（函数调自己），回溯几乎都用递归实现。
DFS（深度优先搜索） 是一种遍历策略（一条路走到底再回头）。回溯就是「在决策树/状态空间上做 DFS」。
回溯特指这种「做选择—递归—撤销选择」、带状态还原的 DFS，强调尝试并撤销。

可以说：回溯 = DFS + 状态的做与撤销。图/树遍历里的 DFS 不一定需要「撤销」，而回溯的灵魂正是撤销。

七、复杂度：为什么回溯通常是指数级

回溯的复杂度约等于决策树的节点数 × 每个节点的处理代价。因为是穷举，树的规模往往是指数或阶乘级：

全排列：O(n × n!)（n! 个叶子）；
子集：O(n × 2^n)（每个元素选或不选）；
N 皇后：接近 O(n!)（配合剪枝远小于此）。

所以回溯适合规模较小的搜索问题；规模大时要么靠强剪枝，要么换动态规划/贪心等更优方法。

八、把状态、选择与撤销画成决策树

本题递归状态的精确定义是：path 保存根到当前节点的选择，选择列表给出可扩展分支，撤销后必须恢复进入该层前的状态。状态含义越清楚，结束条件、候选范围和去重位置越容易从题意推出。

进入节点：检查当前状态与剩余目标
枚举候选：先判断约束和剪枝条件
做选择：同步修改 path / used / 约束集合
递归下一层
撤销选择：恢复到进入本节点前的状态

带数字推演：排列 n 个不同元素有 n! 个叶子，复制每个长度 n 的答案使输出成本至少 Ω(n·n!)。画树时只需展开能体现“同层选择”和“纵向递归”区别的两三层，并标出被剪掉的分支，便能解释去重或剪枝为什么不会漏解。

记忆钩子：回溯不是“递归试一试”，而是维护状态不变量；做选择与撤销必须镜像，剪枝必须证明被删分支不可能产生答案。

九、复杂度、剪枝代价与实现边界

关键实现边界是：剪枝只能删除已证明不可能产生合法解或更优解的分支；共享可变状态要明确所有权。回溯复杂度不能只写一个固定模板，应说明树深、每层分支数、合法叶子数以及复制答案的成本。

维度	自检问题
状态	参数能否唯一描述当前节点
候选	是否遗漏合法选择或重复枚举
剪枝	条件是必要条件还是拍脑袋
撤销	path、标记和计数是否全部恢复
输出	保存的是快照还是共享可变引用

测试应包含无解、唯一解、多解、最小规模、全部候选相同或冲突密集的输入。对可变字符串、棋盘和标记数组，还应在递归返回后断言状态与进入前一致；这类断言比只比较最终答案更容易定位撤销错误。

十、常见误区与追问

误区：递归就是回溯。 回溯还包含枚举选择、约束检查和状态恢复。
误区：撤销选择可以放在循环结束后统一做。 每个分支返回后都必须立即恢复对应选择。
误区：剪枝越多越好。 错误剪枝会漏解，必须有可证明的必要条件。
追问：三要素是什么？ 路径、当前可选集合、结束条件。
追问：回溯复杂度怎么分析？ 看决策树节点数、每节点检查代价和复制答案成本。
追问：何时改用 DP？ 只求计数/最优值且大量状态重复时，可记忆化或动态规划。

十一、加强记忆

回溯 = 决策树上的 DFS，动作恒为「做选择 → 递归 → 撤销选择」。三要素：路径（已选）、选择列表（能选，用 start（组合/子集）或 used[]（排列）界定）、结束条件（收集解时记得拷贝一份）。灵魂是做与撤销对称（改过的状态递归后全还原），提速靠剪枝（合法性/可行性/去重）。它是穷举，复杂度通常指数或阶乘级，适合小规模搜索。

简化版

详细版