89. 格雷编码

题意

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

集）。

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

难度

中等

示例

示例 1：

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

输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2：

输入：nums = [0]

输出：[[],[0]]

分析

要枚举一个集合的所有子集，我们可能第一时间想到的是递归与回溯算法，但是这类算法

通常会使用大量的栈空间，我们不妨采用另外一种方法——二进制枚举。

二进制枚举的核心思想是利用二进制数的每一位来表示某种状态或选择，从而枚举出所有

可能的组合或子集。

以下是对二进制枚举的基本原理进行说明：

①. 基本概念: 在二进制数中，每一位只能是 0 或 1，其中 0 通常表示“不选择”或“假”，而 1

表示“选择”或“真”。

②. 应用场景: 当你有一个长度为 n 的集合或数组，并且你想要枚举其所有可能的子集时，

二进制枚举是一种有效的方法。因为一个长度为 n 的集合总共有 2^n 个子集（包括空集

和整个集合本身）。

看下面的表达式。

$ C^{0}{n} + C^{1}{n} + + C^{n-1}{n} + C^{n}{n} = 2^{n} $

$ C^{m}_{n} $ 的含义是从 $ n $ 个不同元素中取出 $ m(m n) $ 个元素的所有不同排列个

数，所以上述表达式的意思是 $ n $ 个元素能组合出多少种方式。

③. 枚举过程:

• 对于长度为 n 的集合，可以使用从 0 到 2^n - 1 的整数进行枚举。

• 对于每个整数，将其转换为二进制表示。此时，二进制数中的每一位都对应集合中的

一个元素，1 表示选择该元素，0 表示不选择。

• 例如，对于集合{A, B, C}，整数 5 的二进制表示是 101，表示子集{A, C}。

④. 示例:

如果有一个集合{A, B, C}，则二进制枚举的结果为：

000 -> {}

001 -> {C}

010 -> {B}

011 -> {B, C}

100 -> {A}

101 -> {A, C}

110 -> {A, B}

111 -> {A, B, C}

⑤. 优点:

• 二进制枚举是一种非常直观且易于实现的方法。

• 它可以高效地枚举所有可能的组合，尤其适用于解决与组合、子集相关的问题。

这就是我们进行二进制枚举的根本。那么重复的元素要如何去除呢？

如果有两个重复的元素，则会导致单独选了这两个元素的子集相同。既然相同，直接跳过

即可，我们可以将整个 nums 排序一遍，然后进行二进制枚举，遇到前后一样，并且不是

前后两个同时选择的方案，就直接跳过，不加入结果中即可。

例如，考虑数组 [1,2,2]，我们只为第一个 2 生成子集 [2]，不为第二个 2 生成相同的子

集。

来看完整题解。

class Solution {

// res 存储最终的子集列表

List<List<Integer>> res = new ArrayList<>();

// t 临时存储每个子集

List<Integer> t = new ArrayList<>();

public List<List<Integer>> subsetsWithDup(int[] nums) {

// 首先对数组进行排序，确保重复的数字相邻

Arrays.sort(nums);

int siz = nums.length;

// chosen 的范围从 0 到 (2^siz)-1, 表示所有可能的子集

for (int chosen = 0; chosen < (1 << siz); chosen++){

t.clear(); // 清空临时列表

boolean insFlag = true; // 标志位，表示是否应该插入子集

// 遍历每一个数字

for (int i = 0; i < siz; i++) {

 // 如果 chosen 的第 i 位是 1，那么 nums[i] 应该被添加到子集中

if ((chosen & (1 << i)) != 0){

// 如果 nums[i] 和前一个数字相同，且 chosen 的第 i-1 位为 0（意味着

nums[i-1] 不在子集中）

// 那么这是一个重复子集，因此我们设置 insFlag 为 false，并中止循环

if (i > 0 && (nums[i] == nums[i - 1]) && (chosen & (1 << (i - 1))) ==

0) {

insFlag = false;

break;

}

t.add(nums[i]); // 把 nums[i] 添加到临时子集

}

}

// 如果这不是一个重复子集，就添加到 res 中

if (insFlag) {

res.add(new ArrayList<>(t));

}

}

return res;

}

}

当 nums = [1,2,2] 时，我们可以使用题解中的方法来模拟整个过程。

首先，对 nums 进行排序（已经是排序的，不用再排序）。

接着，使用二进制枚举来生成所有可能的子集。

1. 0 (二进制: 000)：不选择任何元素 → []

2. 1 (二进制: 001)：选择第一个元素 → [1]

3. 2 (二进制: 010)：选择第二个元素 → [2]

4. 3 (二进制: 011)：选择第一个和第二个元素 → [1,2]

5. 4 (二进制: 100)：选择第三个元素 → [2]，但是这里注意，第三个元素和第二个元素

相同，且第二个元素没有被选中，因此我们跳过这个选择，避免产生重复的子集。

6. 5 (二进制: 101)：选择第一个和第三个元素 → [1,2]，但是这是和第四个选择重复的

子集，所以也被跳过。

7. 6 (二进制: 110)：选择第二个和第三个元素 → [2,2]

8. 7 (二进制: 111)：选择所有元素 → [1,2,2]

通过上述模拟，我们可以得到所有的子集：

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

关键的步骤是如何避免重复。在这个题解中，通过检查当前元素与前一个元素是否相同，

并根据前一个元素是否被选中来决定是否跳过当前选择，从而避免了重复子集的产生。

来看题解的效率。

090.%E5%AD%90%E9%9B%86II-20231015173530.png

总结

本题是 078.子集 的加强版，总体上只相差了对重复元素的处理，我们处理的方法也是抓

住关键，跳过它。

力扣链接：https://leetcode.cn/problems/subsets-ii/