02.6.1.4 回溯综合与去重
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.6 回溯与递归 / 02.6.1 递归与回溯框架
02.6.1.4-001 回溯结果去重有哪几类来源?
一句话结论
重复解来自两类:一是元素值相同但位置不同导致同值被多次选入(同值重复),二是选择顺序不同生成相同序列(顺序重复);前者靠排序 + 同层跳过,后者靠 start 固定选择方向。
概念解释
- 同值重复:相等元素互换位置产生同序列。
- 顺序重复:先选 1 后选 2 与先选 2 后选 1。
原理流程
- 观察重复解的差异点。
- 判断是值重复还是顺序重复。
- 分别选去重手段。
代码 / 图示
[1a,1b] 选一个 → [1] 重复:同值重复
[1,2] 与 [2,1]:顺序重复
常见误区
- 误区:一种去重手段通吃所有题型;正解:组合、排列、子集手段不同。
- 误区:去重只在结果集用 Set 兜底;正解:应在搜索层避免生成重复分支。
追问
- Q:排列重复属于哪类? A:同值重复,顺序本身要保留。
- Q:组合重复属于哪类? A:顺序重复为主,start 固定方向。
02.6.1.4-002 排序后相邻同值跳过怎么写?
一句话结论
先排序使相等元素相邻;同层循环中若 nums[i]==nums[i-1] 且前一同值未在路径上,跳过当前分支;这样同一层相同值只取第一个,避免兄弟分支生成重复解。
概念解释
- 相邻:排序后重复值紧挨。
- 同层:同一 for 循环。
原理流程
- 排序。
- 遍历判相等与 used。
- 重复则 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。
原理流程
- 相等元素比较。
- 看前一元素 used 状态。
- 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 记录本层已选过的值;当前值已在集合中则跳过,否则加入并递归;等价于同层同值只选一次。
概念解释
- 层内集合:兄弟分支已用值。
- 生命周期:随该层递归结束丢弃。
原理流程
- 每层新建 Set。
- 候选值在集合中则跳过。
- 选中后加入集合再递归。
代码 / 示例
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:本层候选起点。
- 方向:只增不减。
原理流程
- 本层从 start 遍历到末尾。
- 选中 i,下一层传 i+1。
- 撤销后试下一个 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 避免顺序重复。
概念解释
- 不可重复:元素消耗一次。
- 可重复:元素可多次使用。
原理流程
- 明确题目是否允许重复取同一元素。
- 决定递归传 i 还是 i+1。
- 去重条件按对应写法调整。
代码 / 示例
// 可重复: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 枚举;同层遇到与前一相等的值,若前一同值未选(本层跳过不选分支)则当前也跳过,避免生成相同子集;每个节点都收集子集。
概念解释
- 子集:路径任意长度都入结果。
- 重复:相同元素不同选法产生同集合。
原理流程
- 排序。
- 同层同值只走第一分支。
- 节点收集当前路径。
代码 / 示例
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 开始枚举未用元素,去重只挡同值兄弟分支。
概念解释
- 排列:每层遍历全部候选。
- 去重:同值兄弟只取第一个。
原理流程
- 排序与 used。
- 遍历未用元素。
- 同层重复跳过,递归撤销。
代码 / 示例
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 剪枝;每个候选位置最多用一次。
概念解释
- 不可重复:位置只选一次。
- 去重:同值不同位置产生同组合。
原理流程
- 排序。
- 同层重复跳过。
- 选中后下一层 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 计数(硬币凑和),不是回溯枚举。
概念解释
- 选取约束:可否重复、个数限制。
- 计数口径:有序/无序。
原理流程
- 对照候选是否重复。
- 明确位置可否重用。
- 判断要枚举还是计数。
代码 / 示例
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 结果收集在叶子还是每个节点?
一句话结论
组合、排列、定长子集在路径长度/和达标时(叶子)收集;子集类任意长度都合法,在每个进入节点收集;按“合法解对应决策树哪一层”判断,收集点写错会多收或漏收。
概念解释
- 叶子收集:达到目标长度/和。
- 节点收集:前缀本身即合法。
原理流程
- 判断前缀是否已是合法解。
- 是则节点收集。
- 否则继续到叶子收集。
代码 / 示例
子集:进入即 add;组合 C(n,k):size==k 才 add
常见误区
- 误区:子集只在叶子收集;正解:会漏掉所有非空前缀子集。
- 误区:组合在中间节点收集;正解:长度未达标不是合法组合。
追问
- Q:收集后还要继续递归吗? A:达标即返回;未达标可继续扩展。
- Q:空集什么时候加入? A:子集问题初始路径为空即收集。
02.6.1.4-012 路径与原数组索引怎么对应?
一句话结论
路径存元素值还是下标取决于去重与重复值处理:有重复值时存下标便于 used 判断,输出时再取值;无重复值可直接存值;start/used 都围绕下标工作。
概念解释
- 存下标:位置唯一,便于标记。
- 存值:结果直观,重复值易混。
原理流程
- 判断候选是否有重复值。
- 重复值路径存下标。
- 收集结果时映射为值。
代码 / 示例
path.add(i); // 存下标
res.add(path.stream().map(k -> nums[k]).toList());
常见误区
- 误区:重复值存值导致 used 无法区分位置;正解:存下标更稳。
- 误区:结果直接存下标;正解:输出要转成元素值。
追问
- Q:无重复值能存值吗? A:可以,used 按下标另存。
- Q:下标与值映射在什么时候做? A:收集结果时统一转换。
02.6.1.4-013 重复解产生的两个根本原因是什么?
一句话结论
一是同一层对相等值做了多次等价选择(同值重复),二是选择顺序未被约束导致相同集合被不同顺序生成(顺序重复);排查重复解时先定位属于哪一类。
概念解释
- 同值重复:兄弟分支等价。
- 顺序重复:方向未固定。
原理流程
- 对比重复解序列。
- 看是值相同位置不同还是顺序不同。
- 对应去重手段。
代码 / 图示
同值:[1a,2] 与 [1b,2]
顺序:[1,2] 与 [2,1]
常见误区
- 误区:把顺序重复当成同值重复处理;正解:先分类再动手。
- 误区:只在最终结果集去重;正解:搜索层去重才避免无效分支。
追问
- Q:结果集 Set 兜底可行吗? A:可行但低效,仅作校验手段。
- Q:怎么验证去重完整? A:小用例对比去重前后解集合。
02.6.1.4-014 什么时候需要状态哈希判重?
一句话结论
网格/棋盘搜索中,若同一布局状态可由不同路径到达,且后续只依赖布局,可用状态哈希(掩码/序列化)记录已访问布局,避免重复搜索;路径顺序本身是解的一部分时不判重。
概念解释
- 布局状态:占用位置集合。
- 重复到达:不同路径同布局。
原理流程
- 抽取布局可编码状态。
- 已访问则跳过。
- 未访问登记后递归。
代码 / 示例
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 剪枝与去重的配合顺序是什么?
一句话结论
先排序(去重前提),再在循环内做合法性/超限剪枝,然后同层去重跳过,最后做选择递归;顺序保证剪枝条件基于有序候选,去重不被残留状态干扰。
概念解释
- 排序:去重与顺序剪枝前提。
- 剪枝:剔除无解分支。
- 去重:剔除等价分支。
原理流程
- 排序候选。
- 超限/不足剪枝。
- 同层去重后递归。
代码 / 示例
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 兜底会保留大量无效枚举。
概念解释
- 兜底:结果层合并。
- 代价:重复分支仍被枚举。
原理流程
- 路径序列化为键。
- 入 Set 自动去重。
- 最后转列表输出。
代码 / 示例
Set<List<Integer>> res = new HashSet<>();
// 收集时 add(path 副本)
常见误区
- 误区:用 Set 就不用排序去重;正解:枚举成本仍在,Set 只合并结果。
- 误区:List 直接入 Set 不去重;正解:List 的 equals 按元素比较,可作键。
追问
- Q:序列化键怎么写? A:拼接元素加分隔符,避免歧义。
- Q:什么题适合兜底? A:重复来源复杂、规模小的题。
02.6.1.4-017 对称剪枝怎么利用问题对称性?
一句话结论
问题具有左右/上下对称时,固定第一个选择的位置即可只搜一半,其余由对称得到;如对称棋盘、对称括号;剪枝必须确认对称不改变解的合法性。
概念解释
- 对称性:镜像解等价。
- 固定首支:避免镜像重复枚举。
原理流程
- 识别对称方向。
- 固定代表分支。
- 结果按对称还原或只计代表。
代码 / 示例
对称树:固定左支先搜,右支镜像不再重复展开
常见误区
- 误区:不对称问题强行对称剪枝;正解:先确认约束在镜像下不变。
- 误区:对称剪枝后忘记补镜像解;正解:若要全部解需还原镜像。
追问
- Q:N 皇后能用对称剪枝吗? A:可按列对称减半计数,需谨慎核对。
- Q:对称剪枝属于哪类优化? A:等价分支剔除,与去重同类。
02.6.1.4-018 回溯中字符串/浮点状态怎么处理?
一句话结论
字符串不可变,拼接产生新串可直接传参无需撤销;浮点比较避免直接相等,用误差范围;状态键含字符串时注意编码一致性;路径用 StringBuilder 复用则需回退删除。
概念解释
- 不可变:String 每次新对象。
- 浮点:精度误差。
原理流程
- 判断状态类型。
- 不可变直接传,可变容器撤销。
- 浮点按容差比较。
代码 / 示例
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 回溯复杂度与解的规模是什么关系?
一句话结论
总工作量约等于“枚举分支数 × 单分支代价”,合法解越多构造结果的拷贝成本越高;剪枝与去重降低分支冗余,但最坏仍按满决策树估;输出空间随解的数量线性增长。
概念解释
- 枚举分支:决策树节点。
- 单解代价:路径/棋盘构造。
- 输出规模:解数 × 单解长度。
原理流程
- 估分支量级。
- 乘单解构造代价。
- 单列输出空间。
代码 / 示例
解数 S,单解长度 k:时间 O(S·k) 量级,输出 O(S·k)
常见误区
- 误区:只报解的数量不报构造代价;正解:拷贝/序列化也要计入。
- 误区:剪枝后时间按理想值承诺;正解:先报最坏再谈实际收益。
追问
- Q:结果集占多少空间? A:S·k,属输出空间。
- Q:怎么降低输出成本? A:延迟构造或共享不可变前缀。
02.6.1.4-020 回溯题排查 checklist 有哪些?
一句话结论
排查顺序:结束条件与收集点 → 候选边界与 start/used → 做选择与撤销成对 → 结果拷贝 → 排序与同层去重 → 剪枝条件安全 → 复杂度与边界用例;逐项对照可定位多数错误。
概念解释
- 正确性链路:条件、现场、拷贝、去重。
- 性能链路:剪枝、复杂度。
原理流程
- 先跑最小用例看收集结果。
- 对照模板查现场与拷贝。
- 补重复元素与边界用例。
代码 / 示例
checklist:收集点 / 候选范围 / 撤销 / 拷贝 / 去重 / 剪枝 / 复杂度 / 边界
常见误区
- 误区:一上来调复杂度;正解:先保证解不重不漏,再优化分支。
- 误区:只用无重复用例验证;正解:必须含重复元素与空/单元素边界。
追问
- Q:结果缺解先查什么? A:候选范围、撤销是否误杀、收集点。
- Q:结果重复先查什么? A:排序与同层去重、start 方向。