回溯

一句话：回溯就是 DFS 加上一句”撤销现场”——穷举所有可能解的通用框架是「做选择 → 递归进入下一层 → 撤销选择」，三步缺一不可。写不出撤销那一步，是这类题最常见的翻车原因。

固定框架：选择、递归、撤销

46-全排列、78-子集、39-组合总和、22-括号生成、51-N皇后 看起来是完全不同的问题，但代码骨架一模一样：

void backtrack(路径, 选择列表):
    if 满足结束条件:
        记录路径的拷贝; return
    for 选择 in 选择列表:
        做选择(路径.add(选择))
        backtrack(路径, 新的选择列表)
        撤销选择(路径.removeLast())

“记录路径的拷贝”和”撤销选择”是最容易漏掉的两步：路径通常用一个可变的 List 复用，如果直接把这个引用存进结果集，后续的撤销/添加会连带修改已经”记录”的答案——必须拷贝一份新的 List。撤销选择如果漏写，路径会一直增长，后续分支会带着不属于自己的选择继续递归。

怎么判断该不该剪枝

39-组合总和、40-组合总和II、90-子集II 都涉及去重/剪枝：同一层的选择列表里，如果排序后相邻两个值相等，且前一个值在本层还没被选（说明它在回溯时被撤销过），就跳过当前值——这是”同一层去重”和”同一条路径内允许重复使用”的标准写法，专门用来处理”结果不能重复但输入有重复元素”的题目。

判断能否剪枝的一般原则：如果当前的部分解已经不可能满足最终条件（比如组合总和已经超过目标值，且候选数组已排序），就没必要往下递归——排序后提前 break 而不是 continue，可以把剩下的候选一并跳过，这是回溯题里最常见的可提前终止场景。

递归树的”层”与”树枝”

78-子集（位运算）和回溯解法体现了同一个问题的两种视角：回溯是在显式遍历一棵”选或不选”的决策树，每一层对应一个元素，每个分支对应”选”或”不选”；位运算解法是把这棵决策树”压平”成 2^n 个位掩码直接枚举，两者遍历的是同一个搜索空间，只是数据结构不同（显式递归 vs 隐式二进制编码），复杂度分析见位运算。

37-解数独、79-单词搜索 是回溯在二维网格上的应用，区别只是”选择列表”从”剩余候选数字/单词”变成了”当前格子能填的数字”或”下一步能走的方向”，撤销现场对应”把格子清空”或”把访问标记复原”，框架不变。