题型地图 56天全屏 141题

当前：LC78 · 子集 · 首次出现于 Day 26 · 路径：顶栏「56天打卡」→ 点击 LC 题号 → 逐题动画

32 / 141回到 Day 26 卡片 141 题索引

LC78

子集：三件装备，能组成多少种出征方案？

每个元素只有两个命运：带上，或者不带。把所有命运组合起来，就是所有子集。

nums = [1, 2, 3]

装备

OFFON

装备

OFFON

装备

OFFON

result 结果池

—

共 0 / 8 个子集

时间

O(n · 2^n)

辅助空间

O(n)

输出空间

O(n · 2^n)

为什么是 2^n？

nums = [1, 2, 3]

元素 1：选 or 不选 → 2 种

元素 2：选 or 不选 → 2 种

元素 3：选 or 不选 → 2 种

总方案数 = 2 × 2 × 2 = 8

回溯的任务不是猜答案，而是把这 2^n 条路径全部走一遍。

LC77 组合 vs LC78 子集

LC77 只收集长度为 k 的 path，例如 C(3,2) 只要 [1,2]、[1,3]、[2,3]。

LC78 要所有长度：空集 []、单元素、双元素、全集都要。子集 = 每个元素的 ON/OFF 组合。

1/55 · 题目理解

题目：返回 nums 的所有子集

给定无重复元素的数组 nums，返回所有可能的子集（幂集）。例如 nums=[1,2,3] 要返回 8 个子集。

子集不要求连续、不要求排序，只关心每个元素在不在集合里。

index

path

[]

res 数量

当前动作

理解题意

二叉决策树舞台

左=skip · 右=take

path 背包

[] 空背包

res 已收集

尚无子集

TypeScript · 选/不选

1function subsets(nums: number[]): number[][] {
2  const res: number[][] = [];
3  const path: number[] = [];
4 
5  function dfs(index: number) {
6    if (index === nums.length) {
7      res.push([...path]);
8      return;
9    }
10 
11    dfs(index + 1);
12 
13    path.push(nums[index]);
14    dfs(index + 1);
15    path.pop();
16  }
17 
18  dfs(0);
19  return res;
20}

代码旁白

dfs(index)L5, L10, L12

从 nums[index] 开始，继续决定后面的元素要不要进入 path。

pathL3, L11, L13

当前这条路径已经选中的元素，像出征背包。

resL2, L7

所有完整路径的快照，结果池。

res.push([...path])L7

必须复制 path；直接 push(path) 会让后面 pop 污染已收集结果。

path.pop()L13

撤销刚才的选择，回到上一个分叉点，后面的分支才不会被污染。

复杂度（已修正）

时间 O(n · 2^n): 一共有 2^n 个子集，每个子集最坏需要拷贝 path，单次拷贝 O(n)。
辅助空间 O(n): 递归深度最多 n，path 最多存 n 个元素。
输出空间 O(n · 2^n): 最终要返回所有子集，结果本身就这么大。

常见误区

误区 1：以为只收集叶子就够

LC78 有两种写法：选/不选写法在 index === n 时收集；start 枚举写法每进入一个节点就收集当前 path。

误区 2：res.push(path) 没有复制

必须写 res.push([...path])。否则所有结果都会指向同一个数组，后续 pop 会一起变。

误区 3：忘记 path.pop()

push 是进入一个选择，pop 是退出这个选择。没有 pop，后面的分支会被前面的选择污染。

误区 4：把 LC78 和 LC77 混淆

LC77 只要长度为 k 的组合；LC78 要所有长度的子集，包括空集 []。

LC77 / LC78 / LC90 对比

题目	目标	收集条件
LC77 组合	选 k 个	path.length === k
LC78 子集	所有长度都要	选/不选：index === n；start 写法：每节点收集
LC90 子集 II	有重复元素的子集	排序 + 同层去重