回溯
回溯通过选择、递归和撤销枚举候选解。本文负责路径恢复、重复值去重和剪枝。
本文的代码使用递归调用和返回。尚不熟悉调用栈与终止条件时，先读递归。
1. 面试核心
先记住这几条，再读正文- 状态恢复。 回溯通过选择、递归和撤销选择枚举解。返回时恢复路径状态，才能让兄弟分支从同一状态继续。
- 答案保存。 保存可变路径时需复制内容，避免结果共享同一列表。卡 · 决策树与状态恢复
- 重复值去重。 重复值子集按同层去重，下一层仍可选择另一份重复值。卡 · 同层去重
- 输出成本。 n 个互异元素有 2ⁿ 个子集。逐个复制并保存全部子集时，输出成本为 O(n·2ⁿ)，不能只按递归调用次数估算。
2. 决策树与状态恢复
互异元素的每个位置都有选与不选两种决策。走到末端时复制当前路径。
static void subsets(int[] a, int i, java.util.List<Integer> path,
java.util.List<java.util.List<Integer>> result) {
if (i == a.length) {
result.add(new java.util.ArrayList<>(path));
return;
}
subsets(a, i + 1, path, result);
path.add(a[i]);
subsets(a, i + 1, path, result);
path.remove(path.size() - 1);
}
以 i=0、空 path 和空 result 调用。输入 [1,2] 得到 []、[2]、[1]、[1,2]。撤销后，path 恢复到进入本层前的状态。复制列表隔离了后续增删；若元素本身可变，浅复制仍共享元素对象。
3. 剪枝与重复状态
选 k 项时，若 已选数+剩余数<k，当前分支已无法补齐。提前返回就是基于上界的剪枝。按和剪枝时需检查元素符号。正数下的超目标剪枝，遇到负数就失去依据。
3.1 同层去重
去重子集可先排序，再以 start 表示本层候选起点。循环选择时用以下条件跳过同层重复项：
if (i > start && a[i] == a[i - 1]) continue;
选择下标 i 后，下一层从 i+1 开始。输入 [1,1,2] 时，根层只从第一个 1 开始同类分支。下一层仍能选择第二个 1，因此保留 [1,1]。用全局集合禁止值 1 重复，会漏掉这个答案。
排列需要区分已用位置与同层重复值。排序后，常用 used[i] 排除已用位置。若前一相等位置尚未使用，就跳过当前副本。当前路径已经使用前一副本时，则可继续选择。
4. 使用边界
n 个互异元素有 2ⁿ 个子集，输出复制总成本为 O(n·2ⁿ)。路径与递归栈占 O(n)，输出另计 O(n·2ⁿ)。排列输出 n! 个结果时，复制成本为 O(n·n!)。
只求最优值且后续状态重复时，可用动态规划。枚举全部答案仍需承担输出成本。
5 · 面试题卡片
本页题目与参考回答
5.1 回溯中为何要复制 path 再保存答案？
考察重点：可变引用、浅复制与状态恢复。
相关内容：决策树与状态恢复。
参考回答
直接保存会让多个答案引用同一个可变列表。
后续撤销会修改所有这些引用看到的内容。复制列表后，各答案拥有独立的列表结构。元素若可变，还需按题意决定是否复制元素。
5.2 回溯中同层去重与路径去重有何区别？
考察重点：候选等价与位置复用约束。
相关内容：同层去重。
参考回答
同层去重合并值相同的候选分支。
路径去重约束同一个位置是否已经用过。对子集 [1,1,2]，同层跳过第二个 1。下一层仍可选它，从而保留 [1,1]。