复盘 · LC 78 子集

题目

题号：LeetCode 78
名称：子集（Subsets）
难度：Medium
链接：leetcode.cn/problems/subsets
今日代码：78-子集/index.js

题意

给定一个不含重复元素的整数数组 nums，返回其所有可能的子集（幂集）。

解集不能包含重复子集。
返回顺序任意。
边界：nums.length === 1 时应返回 [[], [nums[0]]]；空数组返回 [[]]。

涉及算法

标签	一句话
回溯	每层从 `start` 往后选一个数 push，递归，再 pop 撤销
子集型 DFS	每进入一个节点就把当前路径当作一个合法子集收集
位运算（备选）	`0..2^n-1` 枚举选/不选每一位

教程对照：19 · 递归心智与回溯框架（子集是回溯入门模板题）。

评价我的解法

方向是「按索引往后选、路径 push/pop」，但实现叠了 hasFindArr、depth 两层状态，和初始塞进去的 [[], nums] 搅在一起，既难读也容易漏子集。

我的代码（摘自 78-子集/index.js，不含测例）：

javascript

var subsets = function (nums) {
  const len = nums.length;
  const resArr = [[], nums];
  const hasFindArr = Array.from({ length: nums }).fill(false);
  const curNumArr = [];
  function dfs(depth, index) {
    if (depth === nums.length - 1) {
      return;
    }
    for (let i = index; i < nums.length; i++) {
      if (hasFindArr[i]) {
        continue;
      }
      hasFindArr[i] = true;
      curNumArr.push(nums[i]);
      resArr.push([...curNumArr]);
      dfs(depth + 1, i);
      if (depth !== 0) {
        hasFindArr[i] = false;
      }
      curNumArr.pop();
    }
  }
  dfs(0, 0);
  return resArr;
};

具体问题：

Array.from({ length: nums })：nums 是数组，这里应写 nums.length；当前等价于「长度为数组对象」，行为不稳定。
初始 resArr = [[], nums]：整表 [4,1,0] 被硬塞进去，和 DFS 枚举的子集来源不一致；标准写法是 DFS 入口先 res.push([])，或在递归里统一收集。
hasFindArr 与 depth 重复表达「选到第几层」：子集题只需要 start 索引 + 路径数组，不需要 visited 数组。
if (depth !== 0) hasFindArr[i] = false：depth 为 0 时不撤销标记，会错误跳过某些分支；这是逻辑 bug 隐患。
depth === nums.length - 1 直接 return：人为截断一层，和 for 循环的 i 不同步，漏子集的风险大。
复杂度：每个子集 push([...curNumArr]) 拷贝路径，总输出 size 为 O(n·2^n)，不可避免；但多余状态让常数很大（击败 2.94%）。

小结：回溯「选 / 递归 / 撤」的骨架有了，但被 hasFindArr + depth 绕晕；应退回教程里的 start 型子集模板 默写。

最佳题解

start 索引回溯（每进入递归先收集当前路径）：

javascript

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

  function dfs(start) {
    res.push([...path]);
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);
      dfs(i + 1);
      path.pop();
    }
  }

  dfs(0);
  return res;
};

时间 O(n·2^n)（输出规模下界），空间 O(n) 递归栈（不计结果）。
为何更优：无冗余 visited；start 保证 [1,2] 与 [2,1] 不会重复；入口 res.push([...path]) 自然包含空集，无需预塞 nums 全量。

关联题目

题	为何相关
90. 子集 II	有重复元素，需排序 + 同层去重
46. 全排列	回溯换「used 数组 + 每层扫全体」
39. 组合总和	同一 start 框架，加目标和剪枝
784. 字母大小写全排列	每位选/不选，子集变体

一句话带走

子集回溯：每进一层先把 path 收进答案，再从 start 往后逐个尝试「选这个数 → 递归 → pop 撤销」。

复盘 · LC 78 子集 ​

题目 ​

题意 ​

涉及算法 ​

评价我的解法 ​

最佳题解 ​

关联题目 ​

一句话带走 ​