罗罗编程学习记录
本页内容 展开查看

02.6.1.2 回溯模板与剪枝

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.6 回溯与递归 / 02.6.1 递归与回溯框架

02.6.1.2-001 回溯的本质是什么?

一句话结论

回溯是在决策树上做深度优先搜索:每一步从选择列表里挑一个合法选择,沿分支走到叶子收集解,再回退到上一层换下一个选择;本质是带现场恢复的 DFS。

概念解释

  • 决策树:节点是部分路径,边是一次选择。
  • 路径:已做选择的序列。
  • 选择列表:当前层可选范围。

原理流程

  1. 列出当前所有可选分支。
  2. 逐个尝试合法分支。
  3. 走到叶子记录解,回退试下一支。

代码 / 图示

            根
        /   |   \
      选1   选2   选3
      / \   ...
    叶子 叶子

常见误区

  • 误区:回溯就是枚举暴力;正解:回溯按决策树组织,可剪枝去重,结构更清晰。
  • 误区:回溯只用于排列组合;正解:棋盘、路径、分割等多分支搜索都适用。

追问

  • Q:回溯和 DFS 什么关系? A:回溯是强调选择/撤销与路径记录的 DFS。
  • Q:回溯收集的是节点还是叶子? A:按题意,子集类每个节点都收集,组合类在叶子收集。

02.6.1.2-002 通用回溯模板包含哪几个部分?

一句话结论

模板四件套:结束条件与结果收集、遍历选择列表、合法性判断与剪枝、做选择→递归→撤销选择;路径容器在各层复用,进入前加入、返回后移除。

概念解释

  • 结束条件:路径长度/和/位置达到目标。
  • 选择循环:枚举本层分支。
  • 现场恢复:撤销与做选择对称。

原理流程

  1. 命中结束条件则拷贝路径入结果并返回。
  2. for 遍历选择,非法则跳过。
  3. 加入路径 → 递归 → 移除路径。

代码 / 示例

void backtrack(路径, 选择列表) {
    if (满足结束条件) { res.add(new ArrayList<>(路径)); return; }
    for (选择 : 选择列表) {
        if (不合法) continue;        // 剪枝
        路径.add(选择);
        backtrack(路径, 新选择列表);
        路径.remove(路径.size() - 1); // 撤销
    }
}

常见误区

  • 误区:撤销写在递归之前;正解:必须在递归返回之后恢复。
  • 误区:结束条件只判长度不判合法性;正解:收集前要确认路径满足题目约束。

追问

  • Q:路径容器为什么复用一个? A:避免每层新建列表,撤销即可回到上一层状态。
  • Q:模板里结果为什么拷贝? A:路径后续会被撤销,存引用会被改空。

02.6.1.2-003 做选择和撤销选择为什么必须成对?

一句话结论

路径与标记是跨分支共享的现场,做选择时占用,递归返回后必须还原,否则下一个分支带着上一分支的残留状态,产生错误解或重复解。

概念解释

  • 共享现场:path、used、棋盘标记。
  • 成对:add 对应 remove,置位对应复位。

原理流程

  1. 占用现场。
  2. 递归探索该分支。
  3. 返回后释放现场,再进下一分支。

代码 / 示例

used[i] = true;
path.add(nums[i]);
dfs(...);
path.remove(path.size() - 1);
used[i] = false;   // 与置位成对

常见误区

  • 误区:只撤销 path 不撤销 used;正解:所有被改动的共享状态都要恢复。
  • 误区:递归异常返回时跳过撤销;正解:正常流程内成对,异常分支也要保证复位。

追问

  • Q:不撤销会出现什么现象? A:后续分支误判元素已用,结果缺解或非法解。
  • Q:每次传副本是否就不用撤销? A:是,副本各层独立,但拷贝成本更高。

02.6.1.2-004 为什么收集结果要拷贝路径?

一句话结论

path 是复用的可变列表,回溯过程中不断增删;若直接把引用加入结果,所有结果项都会指向同一个被改空的列表;必须 new ArrayList<>(path) 存入当前快照。

概念解释

  • 引用共享:List 存的是地址。
  • 快照:拷贝当前元素序列。

原理流程

  1. 到达收集点。
  2. 复制 path 当前内容。
  3. 副本加入结果集。

代码 / 示例

res.add(new ArrayList<>(path));  // 拷贝
// 错误:res.add(path);          // 引用会被后续撤销清空

常见误区

  • 误区:基本类型也要拷贝;正解:只有容器/对象引用需要拷贝快照。
  • 误区:字符串也要手动拷贝;正解:String 不可变,直接入结果即可。

追问

  • Q:二维棋盘结果怎么拷贝? A:逐行复制 char[][],不能只复制外层数组。
  • Q:拷贝代价多大? A:单解长度 k,O(k);总代价随解的数量增长。

02.6.1.2-005 回溯和纯 DFS 的区别在哪?

一句话结论

DFS 是遍历图/树节点的手段,关注访问顺序与标记;回溯面向决策树枚举所有合法解,显式维护路径并在分支间撤销现场;回溯一定是 DFS,但 DFS 不一定是回溯。

概念解释

  • DFS:访问节点、记录标记。
  • 回溯:枚举选择序列、收集完整解。
  • 共性:都用递归栈深入。

原理流程

  1. DFS:标记访问 → 深入邻接。
  2. 回溯:选择 → 递归 → 撤销。
  3. 网格题两者常结合。

代码 / 示例

连通块 DFS:访问过即标记,不恢复
回溯排列:用完撤销 used,供其他分支再用

常见误区

  • 误区:网格 DFS 用过的格子也要撤销;正解:连通块统计只需标记访问,排列/路径搜索需撤销。
  • 误区:回溯不用 visited;正解:防止路径重复走入同一元素时需要 used。

追问

  • Q:岛屿数量用回溯吗? A:本质网格 DFS,标记后不撤销。
  • Q:单词搜索用哪种? A:回溯,路径上标记后撤销。

02.6.1.2-006 剪枝的思想是什么?

一句话结论

剪枝是在进入分支前判断该分支不可能产生合法解,直接跳过,避免无效递归;合法解集合不变,只是提前剔除确定失败的子树。

概念解释

  • 无效分支:无论怎么选都不满足约束。
  • 提前终止:少走整条子树。
  • 正确性:剪掉的都是无解分支。

原理流程

  1. 推导当前状态下的必要条件。
  2. 不满足则 continue 或 return。
  3. 满足才继续递归。

代码 / 示例

if (sum + nums[i] > target) continue; // 已超目标,后续更大也超

常见误区

  • 误区:剪枝可能漏掉合法解;正解:剪枝条件必须是“必要不满足”,不能误伤可行分支。
  • 误区:所有回溯都需要剪枝;正解:小规模无需强求,剪枝用于分支爆炸场景。

追问

  • Q:剪枝条件写在循环内还是递归入口? A:都可,循环内按元素剪,入口处按整体状态剪。
  • Q:怎么验证剪枝正确性? A:与不剪枝版本在小用例上对比结果集。

02.6.1.2-007 排序后顺序剪枝怎么用?

一句话结论

先把候选元素升序排序,当前元素已使和超目标时,后面更大的元素也必然超,可直接 break;这是组合总和类最常用的剪枝,前提是同层元素有序。

概念解释

  • 有序:后续元素单调不减。
  • break:同层后续全部排除。

原理流程

  1. 排序原数组。
  2. 循环中累加判断。
  3. 超限即 break,不再向后试。

代码 / 示例

Arrays.sort(candidates);
for (int i = start; i < n; i++) {
    if (sum + c[i] > target) break; // 有序,后面更大
    ...
}

常见误区

  • 误区:未排序也用 break;正解:无序时只能 continue,不能提前终止。
  • 误区:可重复选取问题排序后忘传 i;正解:允许重复则递归传 i,禁止重复传 i+1。

追问

  • Q:为什么去重也要先排序? A:相同值相邻,便于同层跳过。
  • Q:负数元素能顺序剪枝吗? A:不能,正负混合时单调性失效。

02.6.1.2-008 剩余元素不足怎么剪枝?

一句话结论

组合/子集类在还差 k 个元素时,若剩余候选个数不足以补齐,直接返回;长度约束类问题用 剩余元素数 < 缺口 提前终止。

概念解释

  • 缺口:还需选几个。
  • 余量:从当前下标到末尾的元素数。

原理流程

  1. 计算还需数量。
  2. 比较剩余可选个数。
  3. 不足则剪枝。

代码 / 示例

if (k - path.size() > n - i) return; // 剩余元素不够凑齐 k

常见误区

  • 误区:余量按整个数组算;正解:组合用 start 之后的剩余部分。
  • 误区:可重复选取时余量逻辑不变;正解:可重复时候选不消耗,剪枝口径不同。

追问

  • Q:排列类需要这种剪枝吗? A:排列不按剩余个数限制,主要靠 used 与前缀合法性剪。
  • Q:剪枝后结果会少吗? A:不会,只是去掉凑不齐长度的分支。

02.6.1.2-009 重复元素同层去重怎么判断?

一句话结论

先排序,同一递归层内若当前元素与前一个相等且前一个未被使用,说明同层已选过该值,跳过;!used[i-1] 表示前一同值元素在本层不在路径上,避免跨层误杀。

概念解释

  • 同层:同一 for 循环的兄弟分支。
  • 同支:祖先路径上已选。
  • 条件:相等且前未使用 → 同层重复。

原理流程

  1. 排序让相同值相邻。
  2. 遍历判断相等与 used 状态。
  3. 命中重复则 continue。

代码 / 示例

if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;

常见误区

  • 误区:只要相等就跳过;正解:同支(used[i-1]=true)是不同位置选同值,允许保留。
  • 误区:不排序也能相邻去重;正解:必须先排序使重复值相邻。

追问

  • Q:used[i-1] 为 true 为什么不跳? A:前一同值已在当前路径,本层是它的子层,不算重复分支。
  • Q:组合类去重能用 start 代替吗? A:去重条件相同,组合另靠 start 保证顺序。

02.6.1.2-010 剪枝为什么不会影响正确性?

一句话结论

剪枝只删除“不可能满足约束”的分支,被删子树内不存在合法解;只要剪枝条件是合法解的必要条件,保留下来的分支与完整枚举结果一致。

概念解释

  • 必要条件:合法解必须满足。
  • 安全剪枝:违反必要条件才剔除。

原理流程

  1. 写出合法解必须满足的条件。
  2. 不满足该条件即剪。
  3. 对照完整枚举确认结果一致。

代码 / 示例

sum 超 target 的分支不可能回到 target(元素非负)→ 安全剪枝

常见误区

  • 误区:剪枝条件写成充分条件导致误删;正解:剪枝依据必要条件。
  • 误区:带负数时仍按非负剪枝;正解:负数可回补,超限分支未必无解。

追问

  • Q:怎么向面试官证明剪枝安全? A:说明被删分支违反的是必要条件,不含合法解。
  • Q:剪枝优先级怎么排? A:代价小、约束强的判断先做。

02.6.1.2-011 回溯时间复杂度怎么估算?

一句话结论

粗略口径为“解的个数 × 每个解构造代价 × 枚举分支冗余”;无剪枝排列 O(n!)、子集 O(2ⁿ)、组合 O(C(n,k)·k);剪枝会减少实际分支,最坏仍按满决策树估。

概念解释

  • 决策树节点数:枚举分支总量。
  • 单解代价:路径拷贝/构造长度。
  • 最坏口径:不依赖剪枝生效。

原理流程

  1. 定分支因子与深度。
  2. 估算节点/解的数量级。
  3. 乘单解构造代价。

代码 / 示例

全排列:n! 个解,每个拷贝 O(n) → O(n·n!)
子集:2ⁿ 个集合,每个 O(n) → O(n·2ⁿ)

常见误区

  • 误区:回溯复杂度就是递归深度;正解:要看分支数量,深而窄与宽而浅量级不同。
  • 误区:剪枝后时间一定按剪后估算;正解:面试先报最坏,再说明剪枝的实际收益。

追问

  • Q:N 皇后复杂度量级? A:最坏 O(n!) 量级,剪枝后远低于此。
  • Q:构造棋盘结果代价多少? A:每个解 O(n²) 复制棋盘。

02.6.1.2-012 回溯空间复杂度怎么算?

一句话结论

空间 = 递归栈深度 + 路径/标记容器 + 结果存储;辅助空间(不计输出)通常 O(n),结果集大小单独按解的数量与单解长度计。

概念解释

  • 栈深:最长路径长度。
  • 辅助:path、used、棋盘。
  • 输出:res 中所有解。

原理流程

  1. 计最长递归深度。
  2. 加每层复用的标记空间。
  3. 结果空间单独说明是否计入。

代码 / 示例

排列:栈 O(n),used O(n),path O(n);结果 O(n·n!) 属输出

常见误区

  • 误区:把结果集大小算进辅助空间;正解:面试先区分辅助空间与输出空间。
  • 误区:标记数组随分支复制;正解:used 复用并撤销,只占一份。

追问

  • Q:棋盘标记占多少? A:与网格同尺寸 O(mn)。
  • Q:路径拷贝影响空间吗? A:拷贝在结果集里,辅助路径只占一份。

02.6.1.2-013 路径去重和状态去重有什么区别?

一句话结论

路径去重针对“相同元素序列被不同选择路径重复生成”(如 [1,2] 与 [2,1]);状态去重针对“相同搜索状态重复到达”(网格/记忆化);前者靠 start/同层跳过,后者靠 visited 或 memo。

概念解释

  • 路径重复:序列相同、生成路线不同。
  • 状态重复:到达同一状态多次。

原理流程

  1. 判断重复发生在序列层还是状态层。
  2. 序列层用顺序约束与同层跳过。
  3. 状态层用访问标记或缓存。

代码 / 示例

组合:start 保证只往后选,消除顺序重复
网格:visited 防止同一格子重复进入

常见误区

  • 误区:两类去重混在一个 used 里处理;正解:先分清重复来源再选手段。
  • 误区:排列也用 start 去重;正解:排列要全顺序,去重靠同值同层跳过。

追问

  • Q:子集去重属于哪类? A:路径/序列层去重,排序 + 同层跳过。
  • Q:网格绕圈属于哪类? A:状态层重复访问,visited 拦截。

02.6.1.2-014 坐标型回溯的标记怎么管理?

一句话结论

棋盘/网格题用行列、对角线或访问标记记录占用;进入分支置位,递归返回复位;标记可以是布尔数组、哈希集合或位掩码,判断冲突 O(1)。

概念解释

  • 占用标记:列、对角线、格子访问。
  • 成对:置位与复位对称。

原理流程

  1. 计算坐标对应标记下标。
  2. 冲突则跳过,否则置位。
  3. 递归后复位。

代码 / 示例

col[c] = true; d1[r-c+n] = true; d2[r+c] = true;
dfs(...);
col[c] = false; d1[r-c+n] = false; d2[r+c] = false;

常见误区

  • 误区:对角线下标出现负数;正解:主对角线 r-c+n 平移到非负。
  • 误区:标记只置位不复位;正解:兄弟分支需要再次使用该位置。

追问

  • Q:位掩码怎么表示标记? A:整数位 1 表示占用,位运算判断与翻转。
  • Q:坐标标记和 used 数组能合并吗? A:按维度分别记录,避免语义混淆。

02.6.1.2-015 回溯中状态变量如何复用与重置?

一句话结论

跨分支共享的可变状态(path、used、计数)在当前层修改后,必须在递归返回时恢复到进入前的值;不可变参数随栈帧隔离,无需重置;进入分支前先保存需要恢复的值。

概念解释

  • 共享可变:跨分支复用。
  • 隔离参数:栈帧私有。
  • 重置点:递归返回后。

原理流程

  1. 区分可变共享与不可变参数。
  2. 共享状态做修改。
  3. 返回后逐项恢复。

代码 / 示例

int old = flag;
flag = newValue;
dfs(...);
flag = old;  // 恢复

常见误区

  • 误区:用累加计数器后忘记减回;正解:计数类也要对称增减。
  • 误区:在递归内重置整个数组;正解:只恢复本层改动的位置。

追问

  • Q:什么变量不需要重置? A:基本类型参数、不可变字符串、随栈销毁的局部变量。
  • Q:状态重置顺序有要求吗? A:与修改逆序恢复即可,通常成对回写。

02.6.1.2-016 什么时候能用记忆化配合回溯?

一句话结论

当剩余搜索只依赖可枚举的状态(如当前下标、剩余容量、剩余和),且路径历史不影响后续选择时,可用 memo 缓存结果;若解依赖已选集合或路径顺序,记忆化会失真。

概念解释

  • 可缓存状态:与历史路径无关。
  • 路径依赖:历史选择影响后续合法性。

原理流程

  1. 抽取影响后续的状态维度。
  2. 判断历史是否被包含在状态里。
  3. 无路径依赖再缓存。

代码 / 示例

组合总和 IV:状态 (剩余和) 可缓存;排列枚举路径顺序,缓存需谨慎

常见误区

  • 误区:所有回溯都加 memo;正解:带路径/已选集合状态时缓存键无法表达历史。
  • 误区:缓存键漏掉某个维度;正解:状态不完整会复用到错误分支。

追问

  • Q:记忆化搜索和 DP 什么关系? A:记忆化是自顶向下 DP,状态与转移一致。
  • Q:缓存存什么? A:该状态下的可行解数量/最优值,不一定存整条路径。

02.6.1.2-017 忘记撤销选择会出现什么错误?

一句话结论

未撤销会让共享现场残留上一分支状态,导致后续分支误判元素已用/位置被占,表现为结果缺解、出现非法组合,或 used 与 path 长度不一致。

概念解释

  • 残留:本层退出后状态未还原。
  • 传染:兄弟分支读到脏状态。

原理流程

  1. 观察 path/used 在退出分支后的状态。
  2. 对比进入前是否一致。
  3. 定位漏撤销的改动。

代码 / 示例

症状:路径长度异常、元素重复、棋盘残留 Q

常见误区

  • 误区:撤销时按索引 remove 错位置;正解:移除最后加入的元素 path.remove(size-1)。
  • 误区:多个标记只撤销其一;正解:列出本层所有改动项逐项复位。

追问

  • Q:怎么快速定位漏撤销? A:在递归前后打印 path/used 长度对照。
  • Q:用不可变传参能否规避? A:能,但每层拷贝成本上升。

02.6.1.2-018 忘记拷贝结果会出现什么错误?

一句话结论

直接把 path 引用加入结果后,后续撤销会清空同一列表,最终结果里所有项都变成空列表或最后状态;必须在收集点复制快照。

概念解释

  • 引用复用:多个结果项指向同一 List。
  • 快照拷贝:断开后续修改影响。

原理流程

  1. 到达收集点。
  2. 检查存入的是引用还是副本。
  3. 统一改为拷贝入结果。

代码 / 示例

res.add(new ArrayList<>(path));

常见误区

  • 误区:二维结果只复制外层;正解:棋盘/列表内容也要深拷贝。
  • 误区:认为 String 也要拷贝;正解:String 不可变,无需复制。

追问

  • Q:结果全为空列表说明什么? A:存入引用,路径被后续撤销清空。
  • Q:深拷贝代价怎么估? A:单解长度 k,O(k)。

02.6.1.2-019 “枚举选择”与“选/不选”两种模板怎么选?

一句话结论

组合/子集类两种都可:for 枚举当前层选哪个,适合按 start 推进与同层去重;选/不选二分叉更贴合子集决策,代码短但去重需在分叉处判断;排列类必须 for 枚举未选元素。

概念解释

  • for 枚举:一层遍历候选。
  • 二分叉:选或不选当前元素。

原理流程

  1. 按题型选模板。
  2. 组合用 start 控制方向。
  3. 排列用 used 控制可选集。

代码 / 示例

// 选/不选
dfs(i + 1);            // 不选
path.add(a[i]); dfs(i + 1); path.remove(...); // 选

常见误区

  • 误区:排列也用选/不选;正解:排列顺序可变,必须逐个枚举未用元素。
  • 误区:二分叉去重遗漏不选分支;正解:重复值在两支都要判重。

追问

  • Q:哪种模板结果收集时机不同? A:二分叉在叶子收集,for 枚举可在各节点收集子集。
  • Q:模板影响复杂度吗? A:分支总量一致,写法不同。

02.6.1.2-020 回溯框架自检清单包含哪些项?

一句话结论

自检:终止条件与收集点正确、选择列表边界明确、剪枝条件安全、做选择与撤销成对、结果已拷贝、used/标记复位、去重条件与排序到位、复杂度口径可报。

概念解释

  • 正确性:条件、撤销、拷贝。
  • 性能:剪枝与去重。
  • 可表达:复杂度与边界。

原理流程

  1. 对照模板逐项核对。
  2. 用最小用例跑通收集与撤销。
  3. 补边界:空集、单元素、重复元素、超限。

代码 / 示例

清单:结束条件 / 选择范围 / 剪枝安全 / 撤销成对 / 结果拷贝 / 标记复位 / 去重 / 复杂度

常见误区

  • 误区:清单只看主路径;正解:边界与重复元素用例必须覆盖。
  • 误区:复杂度只报辅助空间;正解:输出空间单独说明。

追问

  • Q:回溯题第一步先写什么? A:先定决策树层级与每层选择。
  • Q:怎么判断模板选对了? A:小用例生成的解既不重复也不遗漏。