子集

更新: 7/5/2026 字数: 0 字时长: 0 分钟

LeetCode 78. Subsets

题目描述

给你一个整数数组 nums，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按任意顺序返回解集。

示例：

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

输入：nums = [0]
输出：[[],[0]]

约束：，nums 中元素互不相同。

先想清楚答案有多少个

每个元素都有「选」或「不选」两种状态，个元素相互独立，所以子集总数是个（包含空集和全集）。这个是理解本题的钥匙。

每个元素选或不选

思路拆解：从暴力到最优

想法一：迭代「逐个添加」（暴力思路）

从空集开始，每遇到一个新数字，就把它追加到已有的每个子集后面，生成一批新子集，合并进结果。

以 [1,2,3] 为例：

初始：[[]]
加入 1：把 1 塞进已有的 [] → 新增 [1] → [[], [1]]
加入 2：把 2 塞进 []、[1] → 新增 [2]、[1,2] → [[], [1], [2], [1,2]]
加入 3：同理新增 4 个 → 共 8 个。

点击展开迭代解法

function subsets(nums) {
  let res = [[]];             // 从只含空集开始
  for (const x of nums) {
    const next = [];
    for (const sub of res) {
      next.push([...sub, x]); // 每个已有子集都派生一个"加上 x"的新子集
    }
    res = res.concat(next);   // 合并
  }
  return res;
}

时间：，子集数，每个子集拷贝耗。
空间：，存所有子集。

这个解法完全正确，也很简洁。但它不容易推广到「有重复元素」「限定长度」等变体，而回溯法是这类「枚举所有组合」问题的通用框架，更值得掌握。

想法二：回溯 · 决策树（推荐掌握）

把「求所有子集」看成一棵决策树：从第 0 个元素开始，对每个元素做「选 / 不选」的决策，一路走到底就得到一个子集。

核心思路

站在每个元素面前，都问一句「选它，还是不选它？」——沿着决策树 DFS，走到叶子就收集一个子集。

更常用的等价写法是「从起点 start 开始，依次尝试选入后面的每个元素」：

每进入一次递归，当前的 path 就是一个合法子集，直接加入结果（子集问题的特点：所有节点都是答案，不只是叶子）。
从 start 开始，循环选 nums[i] 加入 path；
递归进入下一层（下次从 i+1 开始，保证不回头、不重复）；
递归返回后撤销选择（path.pop()），恢复现场，尝试下一个分支。

这就是回溯的经典三部曲：选择 → 递归 → 撤销。

为什么用 start 而不是从头遍历？ 因为子集是「组合」不是「排列」——{1,2} 和 {2,1} 是同一个子集。用 start 限定「只能往后选」，就天然避免了重复。

选择-递归-撤销

动态演示

下面的动画完整演示了对 nums = [1,2,3] 的回溯全过程——看决策树如何被逐层深入探索，path 如何随「选择」和「撤销」变化，每个节点如何被收集为一个子集：

步骤 1 / 23收集子集

nums =

路径栈 path（当前选中的元素）

（空）

递归深度：0

已收集子集（1 个）

{∅}

收集子集 #1：{空}。（每进入一层，当前路径就是一个合法子集）

完整代码（JavaScript）

版本 A：回溯 · start 写法（推荐）

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

  const backtrack = (start) => {
    res.push([...path]);       // 每个节点的 path 都是一个合法子集，先收集

    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);      // 选择：把 nums[i] 加入路径
      backtrack(i + 1);        // 递归：从 i+1 继续，保证不回头
      path.pop();              // 撤销：移除，恢复现场
    }
  };

  backtrack(0);
  return res;
}

版本 B：回溯 · 「选 / 不选」二叉写法（更贴近决策树）

function subsets(nums) {
  const res = [];
  const path = [];
  const n = nums.length;

  const dfs = (i) => {
    if (i === n) {             // 到达末尾，path 即一个完整子集
      res.push([...path]);
      return;
    }
    // 分支一：不选 nums[i]
    dfs(i + 1);
    // 分支二：选 nums[i]
    path.push(nums[i]);
    dfs(i + 1);
    path.pop();                // 撤销，恢复现场
  };

  dfs(0);
  return res;
}

版本 C：位运算（利用的二进制枚举）

function subsets(nums) {
  const n = nums.length;
  const res = [];
  for (let mask = 0; mask < (1 << n); mask++) { // 0 ~ 2^n - 1
    const sub = [];
    for (let i = 0; i < n; i++) {
      if (mask & (1 << i)) sub.push(nums[i]);   // 第 i 位为 1 就选
    }
    res.push(sub);
  }
  return res;
}

三种写法怎么选

面试首选版本 A：start 写法最简洁，且能无缝扩展到「组合」「组合总和」等题。
版本 B 最能体现「决策树」思想，适合理解回溯本质。
版本 C 位运算极简，但仅适用于「元素互不相同、无需剪枝」的场景，左右。

复杂度分析

设数组长度为。

解法	空间复杂度	说明
迭代逐个添加		简洁，不易扩展
回溯（start / 二叉）	递归栈	通用框架，推荐
位运算枚举	（不计结果）	极简，适用面窄

为什么都是？ 一共有个子集，生成/拷贝每个子集平均需要，所以时间下界就是 ——这已经是最优，因为光是把个子集写出来就至少要这么多操作。回溯的额外空间只有递归栈深度（不计存储结果本身）。

边界与易错点

易错点

收集时必须深拷贝。res.push([...path]) 要用扩展运算符复制一份快照；若写成 res.push(path)，存进去的是同一个引用，后续 path 变化会污染所有已存结果，最后全变成空数组或乱掉。这是回溯第一大坑。
别忘了撤销（path.pop()）。递归返回后必须弹出刚加入的元素，恢复现场，否则会「串味」——下一个分支会带着上一个分支的残留。选择和撤销要成对出现。
start 保证不回头。递归时传 i + 1 而不是 start + 1 或 0，确保每个元素只在它之后的层被考虑，避免生成 {2,1} 这种重复子集。
空集也是子集。start 写法在递归入口 res.push([...path]) 时，第一次 path 为空就把空集收进去了，天然覆盖。
本题元素互不相同，无需去重。如果是「子集 II」（含重复元素），才需要先排序 + 同层跳过重复（if (i > start && nums[i] === nums[i-1]) continue;）。别把两题的模板搞混。
递归收集位置。子集问题每个节点都要收集（不是只在叶子），这与「排列 / 组合总和」等「只在满足条件时收集」的题不同，位置写错会漏解。

简易解题思路（记忆口诀）

「每个元素问一遍：选它还是不选它；进门先把自己收，往后挨个选一轮；选完递归再撤销，选择撤销成一对。」

拆开记：

口诀	对应操作
每个元素问选不选	决策树本质：每个数两种状态，共个
进门先把自己收	`res.push([...path])`——每个节点都是子集
往后挨个选一轮	`for (i = start; ...)`，用 `start` 防重复
选完递归再撤销	`push → backtrack(i+1) → pop` 三部曲

一句话记住本质：求子集就是在决策树上 DFS——「选一个、往下走、再退回来换下一个」，路径上的每一种组合都是一个子集，一共个。

子集 ​

题目描述 ​

思路拆解：从暴力到最优 ​

想法一：迭代「逐个添加」（暴力思路） ​

想法二：回溯 · 决策树（推荐掌握） ​

动态演示 ​

完整代码（JavaScript） ​

复杂度分析 ​

边界与易错点 ​

简易解题思路（记忆口诀） ​

子集