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

02.6.1.4 回溯综合与去重

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

02.6.1.4-001 回溯结果去重有哪几类来源?

一句话结论

重复解来自两类:一是元素值相同但位置不同导致同值被多次选入(同值重复),二是选择顺序不同生成相同序列(顺序重复);前者靠排序 + 同层跳过,后者靠 start 固定选择方向。

概念解释

  • 同值重复:相等元素互换位置产生同序列。
  • 顺序重复:先选 1 后选 2 与先选 2 后选 1。

原理流程

  1. 观察重复解的差异点。
  2. 判断是值重复还是顺序重复。
  3. 分别选去重手段。

代码 / 图示

[1a,1b] 选一个 → [1] 重复:同值重复
[1,2] 与 [2,1]:顺序重复

常见误区

  • 误区:一种去重手段通吃所有题型;正解:组合、排列、子集手段不同。
  • 误区:去重只在结果集用 Set 兜底;正解:应在搜索层避免生成重复分支。

追问

  • Q:排列重复属于哪类? A:同值重复,顺序本身要保留。
  • Q:组合重复属于哪类? A:顺序重复为主,start 固定方向。

02.6.1.4-002 排序后相邻同值跳过怎么写?

一句话结论

先排序使相等元素相邻;同层循环中若 nums[i]==nums[i-1] 且前一同值未在路径上,跳过当前分支;这样同一层相同值只取第一个,避免兄弟分支生成重复解。

概念解释

  • 相邻:排序后重复值紧挨。
  • 同层:同一 for 循环。

原理流程

  1. 排序。
  2. 遍历判相等与 used。
  3. 重复则 continue。

代码 / 示例

Arrays.sort(nums);
for (int i = start; i < n; i++) {
    if (i > start && nums[i] == nums[i - 1]) continue;
    ...
}

常见误区

  • 误区:组合类用 i>0 判断;正解:组合层起点是 start,应写 i>start。
  • 误区:不排序直接相邻比较;正解:未排序重复值不相邻,条件失效。

追问

  • Q:排列类判断条件带 used 吗? A:带 !used[i-1] 区分同层与同支。
  • Q:去重后顺序变了吗? A:排序改变候选顺序,不影响合法解集合。

02.6.1.4-003 used[i-1] 怎么区分同层与同支?

一句话结论

used[i-1]=false 表示前一同值元素当前不在路径上,即本层兄弟位置,跳过;used[i-1]=true 表示它已在祖先路径上,当前是其子层,允许选择;这是排列去重的关键判据。

概念解释

  • 同支:祖先已选,used 为 true。
  • 同层:兄弟未选,used 为 false。

原理流程

  1. 相等元素比较。
  2. 看前一元素 used 状态。
  3. false 跳同层重复,true 保留同支。

代码 / 示例

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

常见误区

  • 误区:条件写成 used[i-1] 为 true 才跳;正解:反了会误杀合法同支选择。
  • 误区:组合类也加 used 判断;正解:组合用 start 推进,不需要 used 数组。

追问

  • Q:为什么同支允许再选同值? A:不同位置选相等元素是合法排列。
  • Q:去掉 used 判断会怎样? A:同层重复分支全部生成重复解。

02.6.1.4-004 层上哈希集合去重怎么用?

一句话结论

不便排序或元素不可排序时,在每层用一个 HashSet 记录本层已选过的值;当前值已在集合中则跳过,否则加入并递归;等价于同层同值只选一次。

概念解释

  • 层内集合:兄弟分支已用值。
  • 生命周期:随该层递归结束丢弃。

原理流程

  1. 每层新建 Set。
  2. 候选值在集合中则跳过。
  3. 选中后加入集合再递归。

代码 / 示例

Set<Integer> layer = new HashSet<>();
for (int i = start; i < n; i++) {
    if (!layer.add(nums[i])) continue;
    ...
}

常见误区

  • 误区:Set 做成全局跨层;正解:每层独立,否则不同层无法选同值。
  • 误区:先递归后加入集合;正解:进入分支前先登记,挡住后续兄弟。

追问

  • Q:哈希去重与排序跳过哪个快? A:排序跳过 O(1) 判断更省,哈希有额外开销。
  • Q:什么情况用哈希? A:元素无序且不便排序,或键为字符串。

02.6.1.4-005 start 指针怎么保证组合不重复?

一句话结论

组合类每次递归从 start 之后选元素,即只往候选尾部方向取,杜绝回头选;这样 [1,2] 只会按升序生成一次,不会出现 [2,1];选当前 i 后下一层传 i+1。

概念解释

  • start:本层候选起点。
  • 方向:只增不减。

原理流程

  1. 本层从 start 遍历到末尾。
  2. 选中 i,下一层传 i+1。
  3. 撤销后试下一个 i。

代码 / 示例

void comb(int start, ...) {
    for (int i = start; i <= n; i++) {
        path.add(i);
        comb(i + 1, ...);
        path.remove(...);
    }
}

常见误区

  • 误区:下一层传 i 而不是 i+1;正解:禁止重复选取才传 i+1。
  • 误区:排列也用 start;正解:排列要回头选未用元素,用 used。

追问

  • Q:可重复选取传什么? A:传 i,允许再次选当前元素。
  • Q:start 从几开始? A:按题意 0 或 1,与候选下标一致。

02.6.1.4-006 可重复选取与不可重复选取递归参数怎么传?

一句话结论

不可重复选:选中 i 后下一层传 i+1,当前元素不再进入候选;可重复选:下一层传 i,当前元素仍可选;两者都配合 start 避免顺序重复。

概念解释

  • 不可重复:元素消耗一次。
  • 可重复:元素可多次使用。

原理流程

  1. 明确题目是否允许重复取同一元素。
  2. 决定递归传 i 还是 i+1。
  3. 去重条件按对应写法调整。

代码 / 示例

// 可重复:comb(i);不可重复:comb(i+1)

常见误区

  • 误区:可重复问题传 i+1 导致漏解;正解:传 i 保留当前元素。
  • 误区:不可重复问题传 i 导致重复使用同一位置;正解:传 i+1。

追问

  • Q:元素有重复值且不可重复怎么去重? A:排序 + 同层跳过,下标仍 i+1 推进。
  • Q:完全背包视角对应哪种? A:可重复选取,正序枚举。

02.6.1.4-007 子集 II 去重(LC 90)怎么处理?

一句话结论

排序后用“选/不选”或 for 枚举;同层遇到与前一相等的值,若前一同值未选(本层跳过不选分支)则当前也跳过,避免生成相同子集;每个节点都收集子集。

概念解释

  • 子集:路径任意长度都入结果。
  • 重复:相同元素不同选法产生同集合。

原理流程

  1. 排序。
  2. 同层同值只走第一分支。
  3. 节点收集当前路径。

代码 / 示例

for (int i = start; i < n; i++) {
    if (i > start && nums[i] == nums[i - 1]) continue;
    path.add(nums[i]);
    res.add(new ArrayList<>(path));
    dfs(i + 1);
    path.remove(...);
}

常见误区

  • 误区:在叶子才收集;正解:子集在每个非空节点都收集。
  • 误区:不排序直接按值去重;正解:必须先排序。

追问

  • Q:子集 I 无重复元素需要去重吗? A:不需要。
  • Q:结果顺序有要求吗? A:子集内部按选入顺序,集合间顺序不影响正确性。

02.6.1.4-008 排列 II 去重(LC 47)怎么处理?

一句话结论

排序 + used 数组;同层遇到相等元素且前一同值未使用则跳过;与组合不同,排列每层都可从 0 开始枚举未用元素,去重只挡同值兄弟分支。

概念解释

  • 排列:每层遍历全部候选。
  • 去重:同值兄弟只取第一个。

原理流程

  1. 排序与 used。
  2. 遍历未用元素。
  3. 同层重复跳过,递归撤销。

代码 / 示例

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

常见误区

  • 误区:用 start 代替 used;正解:排列顺序可变,start 会漏解。
  • 误区:去重条件不带 used 判断;正解:会误杀同支合法选择。

追问

  • Q:无重复元素排列要 used 吗? A:要,防止同一元素重复进入路径。
  • Q:排列结果总数? A:去重后为多重排列数。

02.6.1.4-009 组合总和 II 去重(LC 40)怎么处理?

一句话结论

候选排序后不可重复选取;同层相邻同值跳过,递归传 i+1;配合和超 target 的 break 剪枝;每个候选位置最多用一次。

概念解释

  • 不可重复:位置只选一次。
  • 去重:同值不同位置产生同组合。

原理流程

  1. 排序。
  2. 同层重复跳过。
  3. 选中后下一层 i+1。

代码 / 示例

if (i > start && c[i] == c[i - 1]) continue;
if (sum + c[i] > target) break;
path.add(c[i]); dfs(i + 1); path.remove(...);

常见误区

  • 误区:传 i 允许重复使用位置;正解:II 类不可重复,传 i+1。
  • 误区:去重条件写 i>0;正解:层起点是 start,写 i>start。

追问

  • Q:组合总和 I 有重复问题吗? A:I 候选无重复,可重复选取传 i。
  • Q:和超 target 为什么 break? A:排序后后续更大,必超。

02.6.1.4-010 组合总和 I/II/III/IV 有什么区别?

一句话结论

I:无重复候选、可重复选、和为 target;II:候选可含重复、不可重复选、去重;III:1~9 选 k 个和为 n;IV:顺序不同算不同组合,本质是 DP 计数(硬币凑和),不是回溯枚举。

概念解释

  • 选取约束:可否重复、个数限制。
  • 计数口径:有序/无序。

原理流程

  1. 对照候选是否重复。
  2. 明确位置可否重用。
  3. 判断要枚举还是计数。

代码 / 示例

I:dfs(i) 可重用;II:dfs(i+1) 去重;III:限定 k 个;IV:dp 计数顺序

常见误区

  • 误区:IV 用回溯枚举;正解:求方案数且有序,DP 更优。
  • 误区:II 忘记候选去重;正解:候选本身可能有重复值。

追问

  • Q:III 的剪枝? A:个数不足/和超限提前返回。
  • Q:IV 外层循环顺序影响什么? A:硬币外层、容量内层得组合数;反之得排列数。

02.6.1.4-011 结果收集在叶子还是每个节点?

一句话结论

组合、排列、定长子集在路径长度/和达标时(叶子)收集;子集类任意长度都合法,在每个进入节点收集;按“合法解对应决策树哪一层”判断,收集点写错会多收或漏收。

概念解释

  • 叶子收集:达到目标长度/和。
  • 节点收集:前缀本身即合法。

原理流程

  1. 判断前缀是否已是合法解。
  2. 是则节点收集。
  3. 否则继续到叶子收集。

代码 / 示例

子集:进入即 add;组合 C(n,k):size==k 才 add

常见误区

  • 误区:子集只在叶子收集;正解:会漏掉所有非空前缀子集。
  • 误区:组合在中间节点收集;正解:长度未达标不是合法组合。

追问

  • Q:收集后还要继续递归吗? A:达标即返回;未达标可继续扩展。
  • Q:空集什么时候加入? A:子集问题初始路径为空即收集。

02.6.1.4-012 路径与原数组索引怎么对应?

一句话结论

路径存元素值还是下标取决于去重与重复值处理:有重复值时存下标便于 used 判断,输出时再取值;无重复值可直接存值;start/used 都围绕下标工作。

概念解释

  • 存下标:位置唯一,便于标记。
  • 存值:结果直观,重复值易混。

原理流程

  1. 判断候选是否有重复值。
  2. 重复值路径存下标。
  3. 收集结果时映射为值。

代码 / 示例

path.add(i);          // 存下标
res.add(path.stream().map(k -> nums[k]).toList());

常见误区

  • 误区:重复值存值导致 used 无法区分位置;正解:存下标更稳。
  • 误区:结果直接存下标;正解:输出要转成元素值。

追问

  • Q:无重复值能存值吗? A:可以,used 按下标另存。
  • Q:下标与值映射在什么时候做? A:收集结果时统一转换。

02.6.1.4-013 重复解产生的两个根本原因是什么?

一句话结论

一是同一层对相等值做了多次等价选择(同值重复),二是选择顺序未被约束导致相同集合被不同顺序生成(顺序重复);排查重复解时先定位属于哪一类。

概念解释

  • 同值重复:兄弟分支等价。
  • 顺序重复:方向未固定。

原理流程

  1. 对比重复解序列。
  2. 看是值相同位置不同还是顺序不同。
  3. 对应去重手段。

代码 / 图示

同值:[1a,2] 与 [1b,2]
顺序:[1,2] 与 [2,1]

常见误区

  • 误区:把顺序重复当成同值重复处理;正解:先分类再动手。
  • 误区:只在最终结果集去重;正解:搜索层去重才避免无效分支。

追问

  • Q:结果集 Set 兜底可行吗? A:可行但低效,仅作校验手段。
  • Q:怎么验证去重完整? A:小用例对比去重前后解集合。

02.6.1.4-014 什么时候需要状态哈希判重?

一句话结论

网格/棋盘搜索中,若同一布局状态可由不同路径到达,且后续只依赖布局,可用状态哈希(掩码/序列化)记录已访问布局,避免重复搜索;路径顺序本身是解的一部分时不判重。

概念解释

  • 布局状态:占用位置集合。
  • 重复到达:不同路径同布局。

原理流程

  1. 抽取布局可编码状态。
  2. 已访问则跳过。
  3. 未访问登记后递归。

代码 / 示例

Set<String> seen = new HashSet<>();
String key = serialize(board);
if (!seen.add(key)) return;

常见误区

  • 误区:把路径轨迹也纳入布局哈希;正解:轨迹是解的一部分时不能合并。
  • 误区:序列化键不稳定;正解:编码需唯一且可复现。

追问

  • Q:状态哈希和 visited 格子有何不同? A:visited 防单路径重复入格;布局哈希防整体状态重复到达。
  • Q:状态空间多大时不可行? A:布局组合爆炸时哈希不可行。

02.6.1.4-015 剪枝与去重的配合顺序是什么?

一句话结论

先排序(去重前提),再在循环内做合法性/超限剪枝,然后同层去重跳过,最后做选择递归;顺序保证剪枝条件基于有序候选,去重不被残留状态干扰。

概念解释

  • 排序:去重与顺序剪枝前提。
  • 剪枝:剔除无解分支。
  • 去重:剔除等价分支。

原理流程

  1. 排序候选。
  2. 超限/不足剪枝。
  3. 同层去重后递归。

代码 / 示例

Arrays.sort(a);
for (int i = start; i < n; i++) {
    if (sum + a[i] > target) break;
    if (i > start && a[i] == a[i-1]) continue;
    ...
}

常见误区

  • 误区:先递归后判断去重;正解:进入分支前拦截。
  • 误区:未排序先做 break 剪枝;正解:无序只能 continue。

追问

  • Q:剪枝和去重条件谁先写? A:超限 break 先,重复 continue 后。
  • Q:顺序影响结果吗? A:只影响效率,合法解集合不变。

02.6.1.4-016 结果集用 Set 兜底去重可行吗?

一句话结论

可行但低效:把路径序列化存入 HashSet 自动合并重复;仅用于小规模校验或搜索层去重困难的场景;正式实现应在回溯层避免生成重复分支,Set 兜底会保留大量无效枚举。

概念解释

  • 兜底:结果层合并。
  • 代价:重复分支仍被枚举。

原理流程

  1. 路径序列化为键。
  2. 入 Set 自动去重。
  3. 最后转列表输出。

代码 / 示例

Set<List<Integer>> res = new HashSet<>();
// 收集时 add(path 副本)

常见误区

  • 误区:用 Set 就不用排序去重;正解:枚举成本仍在,Set 只合并结果。
  • 误区:List 直接入 Set 不去重;正解:List 的 equals 按元素比较,可作键。

追问

  • Q:序列化键怎么写? A:拼接元素加分隔符,避免歧义。
  • Q:什么题适合兜底? A:重复来源复杂、规模小的题。

02.6.1.4-017 对称剪枝怎么利用问题对称性?

一句话结论

问题具有左右/上下对称时,固定第一个选择的位置即可只搜一半,其余由对称得到;如对称棋盘、对称括号;剪枝必须确认对称不改变解的合法性。

概念解释

  • 对称性:镜像解等价。
  • 固定首支:避免镜像重复枚举。

原理流程

  1. 识别对称方向。
  2. 固定代表分支。
  3. 结果按对称还原或只计代表。

代码 / 示例

对称树:固定左支先搜,右支镜像不再重复展开

常见误区

  • 误区:不对称问题强行对称剪枝;正解:先确认约束在镜像下不变。
  • 误区:对称剪枝后忘记补镜像解;正解:若要全部解需还原镜像。

追问

  • Q:N 皇后能用对称剪枝吗? A:可按列对称减半计数,需谨慎核对。
  • Q:对称剪枝属于哪类优化? A:等价分支剔除,与去重同类。

02.6.1.4-018 回溯中字符串/浮点状态怎么处理?

一句话结论

字符串不可变,拼接产生新串可直接传参无需撤销;浮点比较避免直接相等,用误差范围;状态键含字符串时注意编码一致性;路径用 StringBuilder 复用则需回退删除。

概念解释

  • 不可变:String 每次新对象。
  • 浮点:精度误差。

原理流程

  1. 判断状态类型。
  2. 不可变直接传,可变容器撤销。
  3. 浮点按容差比较。

代码 / 示例

dfs(str + c);            // 新串,无需撤销
sb.append(c); dfs(sb); sb.deleteCharAt(sb.length()-1);

常见误区

  • 误区:StringBuilder 递归后不回退;正解:可变容器必须撤销。
  • 误区:浮点用 == 判断;正解:用差值小于 epsilon。

追问

  • Q:字符串拼接复杂度? A:每次 O(k),累计随路径长度。
  • Q:字符数组与 StringBuilder 选哪个? A:复用场景 StringBuilder 更省。

02.6.1.4-019 回溯复杂度与解的规模是什么关系?

一句话结论

总工作量约等于“枚举分支数 × 单分支代价”,合法解越多构造结果的拷贝成本越高;剪枝与去重降低分支冗余,但最坏仍按满决策树估;输出空间随解的数量线性增长。

概念解释

  • 枚举分支:决策树节点。
  • 单解代价:路径/棋盘构造。
  • 输出规模:解数 × 单解长度。

原理流程

  1. 估分支量级。
  2. 乘单解构造代价。
  3. 单列输出空间。

代码 / 示例

解数 S,单解长度 k:时间 O(S·k) 量级,输出 O(S·k)

常见误区

  • 误区:只报解的数量不报构造代价;正解:拷贝/序列化也要计入。
  • 误区:剪枝后时间按理想值承诺;正解:先报最坏再谈实际收益。

追问

  • Q:结果集占多少空间? A:S·k,属输出空间。
  • Q:怎么降低输出成本? A:延迟构造或共享不可变前缀。

02.6.1.4-020 回溯题排查 checklist 有哪些?

一句话结论

排查顺序:结束条件与收集点 → 候选边界与 start/used → 做选择与撤销成对 → 结果拷贝 → 排序与同层去重 → 剪枝条件安全 → 复杂度与边界用例;逐项对照可定位多数错误。

概念解释

  • 正确性链路:条件、现场、拷贝、去重。
  • 性能链路:剪枝、复杂度。

原理流程

  1. 先跑最小用例看收集结果。
  2. 对照模板查现场与拷贝。
  3. 补重复元素与边界用例。

代码 / 示例

checklist:收集点 / 候选范围 / 撤销 / 拷贝 / 去重 / 剪枝 / 复杂度 / 边界

常见误区

  • 误区:一上来调复杂度;正解:先保证解不重不漏,再优化分支。
  • 误区:只用无重复用例验证;正解:必须含重复元素与空/单元素边界。

追问

  • Q:结果缺解先查什么? A:候选范围、撤销是否误杀、收集点。
  • Q:结果重复先查什么? A:排序与同层去重、start 方向。