子集问题如何用回溯法求解？（LeetCode 78）

简化版

求一个数组的所有子集（幂集）。用回溯：从 start 下标往后逐个选，决策树上的每一个节点（不只是叶子）都是一个子集，所以进入递归时就先把当前路径收集下来。关键是用 start 下标保证只往后选、不回头，从而不产生「顺序不同的重复子集」（子集不看顺序）。n 个元素共 2^n 个子集，复杂度 O(n × 2^n)。

详细版

List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    backtrack(nums, 0, new ArrayList<>(), res);
    return res;
}
void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
    res.add(new ArrayList<>(path));            // 每个节点都是一个子集，直接收集
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);                     // 做选择
        backtrack(nums, i + 1, path, res);     // 从 i+1 往后，不回头
        path.remove(path.size() - 1);          // 撤销
    }
}

收集时机不同于排列：排列只在叶子（填满时）收集；子集是每进一个节点就收集（[]、[1]、[1,2]… 全要）。
start 下标：只能选 start 及之后，避免 [1,2] 和 [2,1] 这种重复（子集不看顺序）。
递归传 i+1：同一个元素在一条路径里不重复用。
复杂度 O(n × 2^n)：2^n 个子集，每个收集拷贝 O(n)。

完整版教学

一、子集问题的决策树

子集（幂集）：[1,2,3] 的所有子集是 []、[1]、[2]、[3]、[1,2]、[1,3]、[2,3]、[1,2,3]，共 2^3 = 8 个。

它的决策树和排列不同：每个元素只有「选」或「不选」两种状态，或者换个视角——从 start 开始，依次决定「下一个加谁」。决策树的每一个节点（含根的空集、各中间节点）都对应一个合法子集，而不像排列那样只有叶子才是解。

二、关键：用 start 避免重复（组合型）

子集是组合型问题——[1,2] 和 [2,1] 是同一个子集，不区分顺序。若像排列那样每层从头扫，就会既生成 [1,2] 又生成 [2,1]，重复了。

解决办法是维护一个 start 下标：每层只从 start 及之后的元素里选，选了下标 i 后，递归时把 start 推进到 i+1。这样元素永远按下标递增加入路径，[1,2] 只会以「先 1 后 2」的唯一顺序出现，[2,1] 根本不会被生成。

start 是所有「组合 / 子集」类回溯的标志，作用是只往后选、消除顺序造成的重复。这与排列用 used[] 恰好相对。

三、为什么每个节点都收集

这是子集区别于组合、排列的独特点。组合（如「选 k 个数」）只在路径长度达到 k 时收集；排列只在填满时收集；而子集要所有长度的组合（从空集到全集），决策树上从根到每个节点的路径都是一个合法子集。

所以代码里 res.add(...) 放在函数最开头、for 循环之前——一进入某个节点就把当前路径存下来，无需任何长度判断。空路径 []（根节点）也因此被收进结果，正好对应空集。

四、复杂度 O(n × 2^n)

n 个元素的子集共 2^n 个（每个元素选或不选）。
每个子集收集时要拷贝路径，最长 O(n)。
合计 O(n × 2^n)。这是子集问题不可避免的下界——因为输出本身就有 2^n 个子集、总规模 O(n·2^n)。

五、扩展：子集 II 去重，及「选/不选」写法

子集 II（含重复元素，LeetCode 90）：数组有重复时，先 Arrays.sort，再在 for 里加同层去重 if (i > start && nums[i]==nums[i-1]) continue;（注意是 i > start，跳过同一层里重复的值），逻辑和全排列去重同理。

另一种等价写法——「选或不选」二叉决策：不用 for+start，而是对每个下标 idx 递归两次：一次「选 nums[idx]」、一次「不选」，idx 到末尾时收集。它更直白地体现了「每个元素选/不选」的 2^n 本质，和 start 写法等价，二选一即可。

void dfs(int[] nums, int idx, List<Integer> path, List<List<Integer>> res) {
    if (idx == nums.length) { res.add(new ArrayList<>(path)); return; }
    dfs(nums, idx + 1, path, res);          // 不选 nums[idx]
    path.add(nums[idx]);
    dfs(nums, idx + 1, path, res);          // 选 nums[idx]
    path.remove(path.size() - 1);
}

六、把状态、选择与撤销画成决策树

本题递归状态的精确定义是：每个递归节点代表一个唯一子集，start 保证后续只选更大的原下标，因此每个组合只生成一次。状态含义越清楚，结束条件、候选范围和去重位置越容易从题意推出。

进入节点：检查当前状态与剩余目标
枚举候选：先判断约束和剪枝条件
做选择：同步修改 path / used / 约束集合
递归下一层
撤销选择：恢复到进入本节点前的状态

带数字推演：n=3 时决策树共有 2^3=8 个节点/子集，复制总元素量为 n·2^(n-1)。画树时只需展开能体现“同层选择”和“纵向递归”区别的两三层，并标出被剪掉的分支，便能解释去重或剪枝为什么不会漏解。

记忆钩子：回溯不是“递归试一试”，而是维护状态不变量；做选择与撤销必须镜像，剪枝必须证明被删分支不可能产生答案。

七、复杂度、剪枝代价与实现边界

关键实现边界是：元素重复版本需排序并在同层跳过相等值；若用选/不选二叉树，收集时机在叶子而非每个节点。回溯复杂度不能只写一个固定模板，应说明树深、每层分支数、合法叶子数以及复制答案的成本。

维度	自检问题
状态	参数能否唯一描述当前节点
候选	是否遗漏合法选择或重复枚举
剪枝	条件是必要条件还是拍脑袋
撤销	path、标记和计数是否全部恢复
输出	保存的是快照还是共享可变引用

测试应包含无解、唯一解、多解、最小规模、全部候选相同或冲突密集的输入。对可变字符串、棋盘和标记数组，还应在递归返回后断言状态与进入前一致；这类断言比只比较最终答案更容易定位撤销错误。

八、常见误区与追问

误区：子集只在 path 长度为 n 时收集。 每个中间节点本身就是一个合法子集。
误区：组合型回溯也需要 used。 start 已保证下标递增，通常不需要 used。
误区：复杂度是 O(2^n) 且忽略输出。 复制所有子集的总元素数为 Θ(n·2^n) 的同阶上界。
追问：为什么不会出现 [2,1]？ 递归只向更大下标推进。
追问：子集 II 怎么去重？ 排序后同一层跳过与前一个相等的候选。
追问：迭代怎样做？ 每读一个元素，把现有所有子集复制并追加该元素。

九、加强记忆

子集回溯：用 start 下标只往后选（组合型去重，[1,2] 不再生成 [2,1]），且每进一个节点就收集一次（res.add 放在 for 之前，从空集到全集所有长度都要）。递归传 i+1 防重复用元素。复杂度 O(n × 2^n)。含重复元素用「排序 + if (i>start && nums[i]==nums[i-1]) continue」去重；也可用「每个元素选/不选」的二叉递归等价实现。

简化版

详细版