LC90 子集 II · 逐题动画 · RuntimeScope

RuntimeScope/算法实验台/56 天打卡/141 题/LC90

题型地图 56天全屏 141题

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

← LC85 LC94 →

36 / 141回到 Day 28 卡片 141 题索引

LC90 · 子集 II · 普通人也能看懂版

重复数字安检闸门

用 for-loop 回溯模型讲清「同层去重」：不是禁止选重复数字，而是禁止同一层从第二个重复值再开分支。

nums = [1, 2, 2]

核心规则 · 同层安检闸门

for (let i = start; i < nums.length; i++) {
  if (i > start && nums[i] === nums[i - 1]) continue;
  path.push(nums[i]);
  dfs(i + 1);
  path.pop();
}

关键在 i > start：只比较同层相邻重复，不禁止跨层选两次。

统一模型：for-loop 回溯

本题只用 start 枚举写法，不用「要/不要二叉树」。每一层 for(i=start) 依次尝试可选元素； push → dfs(i+1) → pop 完成回溯；同层 skip 防止等价分支。

1/30 · 题目区

关键步：

Step 0题目区

题目：nums=[1,2,2]，返回不含重复子集

给定可能含重复元素的数组，返回所有不重复子集（幂集）。本题固定 nums=[1,2,2]，正确答案是 6 个子集：[], [1], [1,2], [1,2,2], [2], [2,2]。

为什么

与 LC78 不同，重复元素会让朴素回溯产生重复子集，必须额外去重。

状态表

start	i	path	动作	原因
0	—	[]	理解题意	目标：6 个互不相同的子集

start 线·i 指针·skip 闸门

结果区

[][1][1,2][1,2,2][2][2,2]

TypeScript · for-loop 回溯

1function subsetsWithDup(nums: number[]): number[][] {
2  nums.sort((a, b) => a - b);
3  const res: number[][] = [];
4  const path: number[] = [];
5 
6  function dfs(start: number) {
7    res.push([...path]);
8 
9    for (let i = start; i < nums.length; i++) {
10      if (i > start && nums[i] === nums[i - 1]) continue;
11 
12      path.push(nums[i]);
13      dfs(i + 1);
14      path.pop();
15    }
16  }
17 
18  dfs(0);
19  return res;
20}

复杂度（不计输出）

时间: O(n · 2^n)
辅助空间: O(n)

最坏仍有 O(2^n) 个子集分支；每个子集拷贝 path 最坏 O(n)。排序 O(n log n) 被指数项吸收。

递归深度与 path 长度最多 n；不计输出 res。若计入输出，额外 O(n · 2^n)。

面试表达 · 3 句话

1.先排序，让重复值相邻，才能在同层 for 循环里比较 nums[i] 与 nums[i-1]。
2.同层去重：if (i > start && nums[i] === nums[i-1]) continue —— 只禁止同一层从第二个重复值开分支，不禁止跨层选两次。
3.每进入 dfs 先 res.push([...path]) 收集当前前缀；for 循环里 push → 递归 → pop 完成回溯。

常见误区

误区 1：以为排序后自动去重

排序只是把相同值挨在一起。若不做 i > start && nums[i] === nums[i-1] 的 skip，仍会生成重复子集。

误区 2：以为重复数字不能被选两次

[2,2] 完全合法。规则禁止的是「同一层 for 循环里，从第二个 2 再开一条分支」，不是禁止 path 里出现两个 2。

误区 3：把同层去重写成全局去重

若写成「nums[i] 已在 path 里就 skip」，会把 [2,2] 错误跳过。必须限定 i > start，只比较同层相邻重复。