78. 子集

题目描述

给定一个元素互不相同的整数数组 nums，返回该数组所有可能的子集，也就是幂集。

答案不能包含重复子集，子集的排列顺序和答案的输出顺序均不作要求。

输入：nums = [1,2,3]
输出：[[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]

空集 [] 和数组自身都属于它的子集。

题型判断

每个元素都有“选择”和“不选择”两种可能，因此包含 n 个不同元素的数组共有：

2 × 2 × ... × 2 = 2ⁿ

个子集。

题目要求枚举所有可行结果，适合使用回溯。递归过程中维护当前已经选择的元素，并不断尝试加入后续元素。

与组合题不同，本题没有固定的子集长度，因此：

搜索树中的每个节点都是一个合法子集，而不只是叶子节点。

核心思路：回溯枚举每个子集

递归函数维护两个状态：

path：当前已经选择的元素，也就是一个子集；
startIndex：下一层可以从哪个下标开始选择。

进入递归函数时，当前 path 已经是一个合法子集，所以应该立即保存：

result.push([...path]);

然后从 startIndex 开始枚举下一个元素：

for (let i = startIndex; i < nums.length; i++) {
  path.push(nums[i]);
  backtrack(i + 1);
  path.pop();
}

这就是完整的“做选择、递归、撤销选择”。

为什么需要 `startIndex`

子集只关心包含哪些元素，不关心元素的选择顺序：

[1,2] 和 [2,1] 是同一个子集

如果每一层都从下标 0 开始枚举，就会同时生成 [1,2] 和 [2,1]，还可能重复使用同一个元素。

递归进入下一层时传入 i + 1：

backtrack(i + 1);

表示之后只能选择当前元素右侧的元素。于是每个子集都按照原数组下标递增的唯一顺序生成：

选择下标 0 后，只能选择 1、2、3……
选择下标 1 后，只能选择 2、3、4……

这样既不会重复选择同一个下标，也不会生成顺序不同但内容相同的子集，所以不需要 used 数组。

为什么一进入递归就收集答案

在排列问题中，只有当路径长度等于 n 时才得到完整答案；在固定长度的组合问题中，只有当路径长度等于 k 时才收集答案。

但子集可以有任意长度：

0, 1, 2, ..., n

所以搜索树中的每个节点都代表一个答案：

[]          是空集
[1]         是子集
[1,2]       是子集
[1,2,3]     也是子集

因此收集答案的代码必须放在递归函数开头，而不是只放在叶子节点。

递归树推演

以 nums = [1,2,3] 为例：

[]                         收集 []
├─ [1]                     收集 [1]
│  ├─ [1,2]                收集 [1,2]
│  │  └─ [1,2,3]           收集 [1,2,3]
│  └─ [1,3]                收集 [1,3]
├─ [2]                     收集 [2]
│  └─ [2,3]                收集 [2,3]
└─ [3]                     收集 [3]

可以看到：

根节点对应空集；
每条边表示选择一个新元素；
每个节点对应唯一子集；
越往下，子集包含的元素越多。

JavaScript 实现

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function (nums) {
  const result = [];
  const path = [];

  const backtrack = startIndex => {
    // 每个递归节点都代表一个合法子集
    result.push([...path]);

    for (let i = startIndex; i < nums.length; i++) {
      // 做选择
      path.push(nums[i]);

      // 后续只能选择当前元素右侧的元素
      backtrack(i + 1);

      // 撤销选择
      path.pop();
    }
  };

  backtrack(0);
  return result;
};

代码执行过程

以 nums = [1,2,3] 为例：

调用	当前 `path`	`startIndex`	操作
`backtrack(0)`	`[]`	0	收集空集，从 `1` 开始枚举
`backtrack(1)`	`[1]`	1	收集 `[1]`，可继续选择 `2、3`
`backtrack(2)`	`[1,2]`	2	收集 `[1,2]`，可继续选择 `3`
`backtrack(3)`	`[1,2,3]`	3	收集后无候选，返回
回溯	`[1,2] → [1]`	—	撤销 `2`，再选择 `3`
`backtrack(3)`	`[1,3]`	3	收集后返回
回溯	`[1] → []`	—	撤销 `1`，首层再选择 `2`

当 startIndex === nums.length 时，for 循环自然不会执行，函数直接返回，不需要额外编写终止条件。

状态不变量

每次调用 backtrack(startIndex) 时，都满足：

path 中的元素来自一组严格递增的原数组下标；
path 是当前递归节点所代表的唯一子集；
下标小于 startIndex 的元素不会再被加入当前路径；
函数返回父层之前，path 会恢复到进入本轮选择之前的状态。

因为下标始终递增，同一个下标不会重复使用，同一组元素也不会通过不同顺序再次生成。

正确性说明

不会漏掉子集

任取一个目标子集，将其中元素按照它们在 nums 中的下标递增排列。回溯过程可以依次选择这些下标，并跳过不属于目标子集的元素，因此一定存在一条路径到达这个子集。

不会产生重复子集

每条搜索路径中的下标严格递增，所以任意一组下标只有一种选择顺序。由于题目保证 nums 中的元素互不相同，每组下标对应唯一子集，因此每个子集只会生成一次。

一定覆盖空集

第一次调用时 path 为空，递归函数立即执行：

result.push([...path]);

因此空集自然被加入结果，无需特殊处理。

复杂度分析

输入长度为 n：

子集数量为 2ⁿ；
每次保存子集时需要复制 path，最坏需要 O(n)；
时间复杂度为 O(n × 2ⁿ)；
辅助空间复杂度为 O(n)，包括递归栈和当前路径，不计算返回结果；
结果空间复杂度为 O(n × 2ⁿ)。

更精确地说，所有子集包含的元素总数为：

n × 2ⁿ⁻¹

因为每个元素会出现在一半的子集中。仅输出所有结果本身就需要指数级空间，因此无法把整体时间复杂度优化到低于输出规模。

常见错误

1. 只在叶子节点收集答案

if (startIndex === nums.length) {
  result.push([...path]);
}

在当前“循环枚举下一个元素”的递归结构中，这样只会收集部分路径，遗漏 [1]、[1,2] 等非叶子节点代表的子集。

本题应该在每次进入递归函数时收集当前路径。

2. 忘记复制 `path`

result.push(path); // 错误

所有位置会保存同一个数组引用，之后的 push 和 pop 会影响已经保存的结果。应该保存副本：

result.push([...path]);

3. 下一层仍然传 `startIndex + 1`

backtrack(startIndex + 1); // 错误

下一层应该从“本轮实际选择的位置”之后开始，所以必须传：

backtrack(i + 1);

当循环中的 i 已经大于 startIndex 时，两者含义不同。

4. 每层循环都从 `0` 开始

这会生成 [1,2] 和 [2,1] 等重复结果，还需要额外处理同一下标重复使用的问题。子集应使用 startIndex 保证下标递增。

5. 忘记撤销选择

path.push(nums[i]);
backtrack(i + 1);
// 缺少 path.pop()

递归返回后如果不恢复 path，后续兄弟分支会携带上一个分支的元素，破坏路径状态。

另一种回溯：选或不选

也可以对每个位置明确做二选一：

不选择 nums[index]
选择 nums[index]

这种写法形成一棵高度为 n 的二叉树，只有处理完所有元素的叶子节点才收集答案。

var subsets = function (nums) {
  const result = [];
  const path = [];

  const dfs = index => {
    if (index === nums.length) {
      result.push([...path]);
      return;
    }

    // 不选择 nums[index]
    dfs(index + 1);

    // 选择 nums[index]
    path.push(nums[index]);
    dfs(index + 1);
    path.pop();
  };

  dfs(0);
  return result;
};

这里可以只在叶子节点收集，是因为每条根到叶路径都明确决定了所有元素“选或不选”。它与主解法的递归树结构不同，不能脱离递归定义机械套用收集时机。

迭代写法

初始时只有空集：

result = [[]]

每读取一个数字，就把它加入当前所有已有子集，形成一批新子集。

以 [1,2,3] 为例：

初始：[[]]
加入 1：[[], [1]]
加入 2：[[], [1], [2], [1,2]]
加入 3：[[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

var subsets = function (nums) {
  const result = [[]];

  for (const num of nums) {
    const size = result.length;

    for (let i = 0; i < size; i++) {
      result.push([...result[i], num]);
    }
  }

  return result;
};

必须先保存本轮开始前的 size。如果循环条件直接使用不断增长的 result.length，就会在同一轮反复把当前数字加入新生成的子集。

位掩码写法

n 个元素的选择状态可以用一个 n 位二进制数表示：

第 i 位是 1：选择 nums[i]
第 i 位是 0：不选择 nums[i]

从 0 到 2ⁿ - 1 的每个整数都唯一对应一个子集。

var subsets = function (nums) {
  const result = [];
  const total = 2 ** nums.length;

  for (let mask = 0; mask < total; mask++) {
    const subset = [];

    for (let i = 0; i < nums.length; i++) {
      if (Math.floor(mask / (2 ** i)) % 2 === 1) {
        subset.push(nums[i]);
      }
    }

    result.push(subset);
  }

  return result;
};

这里通过除法读取二进制位，避免 JavaScript 位运算会将数字转换为 32 位有符号整数的限制。题目规模较小时，也可以使用 mask & (1 << i) 判断第 i 位。

与组合、排列的区别

题型	何时收集答案	下一层的选择范围	常用状态
子集	每个递归节点	从 `i + 1` 向后选	`path + startIndex`
固定长度组合	`path.length === k`	从 `i + 1` 向后选	`path + startIndex`
全排列	`path.length === n`	每层从 `0` 开始选未使用元素	`path + used`

一句容易记住的区别是：

子集收集所有节点，组合收集指定层，排列收集叶子节点。

如果输入包含重复元素

本题保证数组元素互不相同。如果输入可能包含重复元素，仅使用 startIndex 仍会生成重复子集。

此时需要先排序，并在同一层跳过相同元素：

nums.sort((a, b) => a - b);

for (let i = startIndex; i < nums.length; i++) {
  if (i > startIndex && nums[i] === nums[i - 1]) continue;

  path.push(nums[i]);
  backtrack(i + 1);
  path.pop();
}

注意子集的同层去重条件是：

i > startIndex

它表示当前元素不是本层的第一个候选。该写法对应「90. 子集 II」。

一句话总结

用 path 表示当前子集，用 startIndex 保证后续只能向右选择；每次进入递归函数都保存当前路径，再依次执行选择、递归和撤销选择，即可生成全部 2ⁿ 个子集。

#78. 子集

#题目描述

#题型判断

#核心思路：回溯枚举每个子集

#为什么需要 startIndex

#为什么一进入递归就收集答案

#递归树推演

#JavaScript 实现

#代码执行过程

#状态不变量

#正确性说明

#不会漏掉子集

#不会产生重复子集

#一定覆盖空集

#复杂度分析

#常见错误

#1. 只在叶子节点收集答案

#2. 忘记复制 path

#3. 下一层仍然传 startIndex + 1

#4. 每层循环都从 0 开始

#5. 忘记撤销选择

#另一种回溯：选或不选

#迭代写法

#位掩码写法

#与组合、排列的区别

#如果输入包含重复元素

#一句话总结