【LeetCode刷题日记】90.子集Ⅱ--- 归纳题解

 🔥个人主页：代码不加冰（欢迎来访） 🎬作者简介：java后端学习者 ❄️个人专栏：LeetCode刷题日记 ，  苍穹外卖日记，SSM框架深入，JavaWeb， ✨命运的结局尽可永在，不屈的挑战却不可须臾或缺！

前言：

大家好，我是代码不加冰，今天是高考的最后一天，感觉还是有点感慨的，去年的这时候我又是什么心情的，可能是难以言表的，并没有想象中的兴奋激动，但也不是解脱吧，高考完还是有一堆的事，成绩考的好不好，志愿怎么报，总之没我们想象中的那么好，有一句话说的挺好：人总是在接近幸福时最幸福，好比是周末，最幸福的时候往往是星期五的下午。所以我们没有必要对未来太过期待，沉下心来，切实的享受当下，用内心去体验，不追怀过去，也不遥想未来。可能这样算是既不悲观也不乐观，每天都是平平淡淡，但是总有那一瞬间，我们会发现，蕴藏在日常生活中的那种幸福感，是来自内心深处的填充，这些以后有时间再讲讲吧，让我们进入到每日的刷题环节。

摘要：

本文通过力扣90题（子集Ⅱ）深入解析回溯算法中的去重问题。作者首先指出本题与子集I的区别在于处理重复元素，并回顾了组合总和II的去重技巧。重点区分了树层去重（防止同一层重复元素产生重复子集）和树枝去重（防止同一路径重复使用元素），通过[1,2,2]示例详细演示了未去重时会产生[2]重复子集的情况。文章对比了used数组在全排列题和子集题中的不同应用，强调子集问题通过startIndex+排序实现树层去重即可。最后总结了used数组在树层/树枝判断中的核心作用，帮助读者掌握回溯去重的本质逻辑。

题目背景：90.子集Ⅱ

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的 子集（幂集）。

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

示例 1：

输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2：
输入：nums = [0]
输出：[[],[0]]

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10

题目分析：  

这道题目和78.子集 区别就是集合里有重复元素了，而且求取的子集要去重。

那么关于回溯算法中的去重问题，在40.组合总和II 中已经详细讲解过了，和本题是一个套路。

这里我们主要复习一下这些易混淆的知识，让我们加深印象，答案是次要的。

一、什么是树层去重

代码中的：

if (i > startIndex && nums[i] == nums[i – 1]) {
continue;
}

就是树层去重。

以：

nums = [1,2,2]

为例：

[]
/ | \\
1 2 2

第一层中：

• 第一个2可以选
• 第二个2不能选

因为：

i > startIndex && nums[i] == nums[i-1]

成立。

否则会产生：

[]
├─ 2
└─ 2

两个完全一样的分支。

所以同一层中，相同元素只保留第一个。

二、什么是树枝去重

树枝去重是：

同一个路径上不允许重复使用某个元素。

例如全排列 II（力扣47）：

boolean[] used;

里面会写：

if (used[i]) continue;

意思是：

1 → 2 → 1

第二次使用同一个位置的1不允许。

这里限制的是：

当前路径（树枝）

而不是当前层。

三、画图理解

树层

同一个父节点的孩子：

[]
/ | \\
1 2 2

这一排叫：同一树层

树枝

从根到叶子的一条路：

[]
|
1
|
2
|
2

这条线叫：树枝

四、为什么90题必须树层去重

假设没有去重：

nums = [1,2,2]

会得到：

[]
├─ 2(第一个)
└─ 2(第二个)

然后：

[2]

会出现两次。

所以要把第二个2剪掉。

即：

if(i > startIndex && nums[i] == nums[i-1])

五、为什么不是树枝去重

如果写成：

if(i > 0 && nums[i] == nums[i-1])
continue;

那么：

[]
└─ 2
└─ 2

第二个2也会被剪掉。

结果：

[2,2]

这个合法答案没了。

因为：子集允许同时选两个2。

所以：

[2]
↓
[2,2]

这条树枝必须保留。

六、一个经典口诀

树层去重

if(i > startIndex && nums[i] == nums[i-1])

作用：

同层相同元素只选一次

常见题：

• 力扣90 子集II
• 力扣40 组合总和II
• 力扣491 递增子序列

树枝去重

if(used[i])

作用：

当前路径上同一个元素不能重复使用

常见题：

• 力扣46 全排列
• 力扣47 全排列II

一句话区分

• 树层去重：防止结果重复。
• 树枝去重：防止同一个元素在一条路径上被重复使用。

举例分析：

对于 力扣90，记住：

if(i > startIndex && nums[i] == nums[i-1])

这是标准的 树层去重 写法。因为题目允许得到 [2,2]，所以绝不能把树枝上的第二个 2 剪掉。

这题就算选了，没有树层去重，会产生什么结果，举例分析

很好，这题最好的理解方式就是把树层去重删掉，然后看看会多出什么结果。

假设：

nums = [1,2,2]

排序后仍然是：

[1,2,2]

并且把这一句删掉：

if (i > startIndex && nums[i] == nums[i – 1]) {
continue;
}

回溯树

根节点：

[]

第一层：

[]
/ | \\
1 2 2
(i=0) (i=1) (i=2)

注意：

• 第一个2来自下标1
• 第二个2来自下标2

虽然来源位置不同，但值一样。

第一条分支

选择第一个2（下标1）：

[]
└── [2]

加入答案：

[]
[2]

继续往下：

[]
└── [2]
└── [2,2]

加入答案：

[2,2]

第二条分支

回到根节点。

选择第二个2（下标2）：

[]
└── [2]

又得到：

[2]

注意：这个 [2] 和前面的 [2] 完全一样。

最终结果

会得到：

[
[],
[1],
[1,2],
[1,2,2],
[1,2], // 重复
[2],
[2,2],
[2] // 重复
]

其中：

[1,2]

出现两次。

[2]

出现两次。

为什么会重复

看根节点：

[]
/ | \\
1 2 2
↑ ↑

两个2在同一层。

它们生成的子集完全一样：

选第一个2 → [2]

选第二个2 → [2]

所以第二个2的整棵子树都是重复的。

树层去重后的效果

有了：

if (i > startIndex && nums[i] == nums[i – 1])

在根节点这一层：

[]
/ |
1 2

第二个2直接跳过。

于是：

[2]

只会生成一次。

为什么 [2,2] 不会被去掉

很多人这里容易误会。

当路径来到：

[]
└── [2]

此时：

startIndex = 2

循环访问：

i = 2

判断：

i > startIndex

即：

2 > 2

结果：

false

不会跳过。

所以：

[]
└── [2]
└── [2]

即：

[2,2]

仍然保留下来。

可以记一个判断方法：

同一层出现两个相同数字
↓
保留第一个，剪掉后面的
↓
树层去重

同一路径上继续选择相同数字
↓
允许
↓
得到 [2,2]

这正是力扣90的核心：同层不能重复选，同枝可以继续选。

used[] 数组本质上是在记录：

某个下标对应的元素，当前是否已经在这条递归路径（树枝）上被使用过。

例如：

nums = [1,2,3]
boolean[] used = new boolean[3];

初始：

used = [false,false,false]

表示三个元素都还没被选。

例子：全排列（力扣46）

代码：

for(int i = 0; i < nums.length; i++) {

if(used[i]) continue;

used[i] = true;
path.add(nums[i]);

backtracking(nums);

path.remove(path.size()-1);
used[i] = false;
}

第一层

选 1：

path = [1]

used = [T,F,F]

表示：

下标0已经用过
下标1没用过
下标2没用过

第二层

循环：

i=0

发现：

used[0] == true

所以：

continue;

不能再选1。

于是只能选：

2 或 3

选2：

path = [1,2]

used = [T,T,F]

第三层

此时：

1 已用
2 已用
3 未用

只能选3：

path = [1,2,3]

used = [T,T,T]

得到一个排列。

used 数组的作用

它解决的问题是：

同一个元素不能重复使用

例如：

[1,1,1]

这种情况不允许。

为什么子集题不用 used

力扣90：

backtracking(nums, i + 1);

每次递归：

i + 1

意味着：

已经访问过的位置
永远不会再访问

所以根本不需要：

used[]

used 在力扣47中的另一个用途

力扣47（全排列Ⅱ）有重复数字：

nums = [1,1,2]

这里会出现经典代码：

if(i > 0
&& nums[i] == nums[i-1]
&& used[i-1] == false)
{
continue;
}

很多人看不懂这里的 used[i-1]。

情况1：used[i-1] == false

第一层

[]
/ \\
1① 1②

如果前面的1没选：

used[0] = false

现在又想选第二个1。

这说明：

两个1在同一层

属于树层重复。

剪掉：

continue;

情况2：used[i-1] == true

[]
└── 1①
└── 1②

前面的1已经在路径上：

used[0] = true

此时选第二个1：

[1,1]

合法。不能剪。

所以：

used[i-1] == false

表示：

前一个相同元素没有被当前路径使用
⇒ 同层
⇒ 去重

而：

used[i-1] == true

表示：

前一个相同元素已经在当前路径中
⇒ 同枝
⇒ 保留

总结

used[] 有两个常见用途：

1. 记录元素是否已被当前路径使用

用于：

• 力扣46 全排列
• 力扣47 全排列Ⅱ

if(used[i]) continue;

防止同一个元素重复加入路径。

2. 辅助判断树层/树枝

用于：

if(i>0 && nums[i]==nums[i-1] && used[i-1]==false)

• used[i-1]==false → 同层 → 去重
• used[i-1]==true → 同枝 → 保留

而力扣90 子集Ⅱ不需要 used[]，因为 startIndex 已经能区分层次，直接用：

if(i > startIndex && nums[i] == nums[i-1])

就完成树层去重了。

用示例中的[1, 2, 2] 来举例，如图所示： （注意去重需要先对集合排序）

从图中可以看出，同一树层上重复取2 就要过滤掉，同一树枝上就可以重复取2，因为同一树枝上元素的集合才是唯一子集

结语：

如果对你有帮助，请点赞，关注，收藏，你的支持就是我最大的鼓励！