Update 0090. 子集 II.md

杨世超 · 杨世超 · commit 144761abcbf8 · 2022-04-06T17:39:01.000+08:00
diff --git a/Solutions/0090. 子集 II.md b/Solutions/0090. 子集 II.md
@@ -5,17 +5,45 @@
 
 ## 题目大意
 
-给定一个整数数组 `nums`，其中可能包含重复元素。
+**描述**：给定一个整数数组 `nums`，其中可能包含重复元素。
 
-要求：返回该数组所有可能的子集（幂集）。
+**要求**：返回该数组所有可能的子集（幂集）。
 
-注意：解集不能包含重复的子集。返回的解集中，子集可以按任意顺序排列。
+**说明**：
+
+- 解集不能包含重复的子集。返回的解集中，子集可以按任意顺序排列。
+- $1 \le nums.length \le 10$。
+- $-10 \le nums[i] \le 10$。
+
+**示例**：
+
+```Python
+输入	nums = [1,2,2]
+输出	[[],[1],[1,2],[1,2,2],[2],[2,2]]
+```
 
 ## 解题思路
 
-先对数组 `nums` 进行排序。回溯的时候，每次遍历从当前位置的下一个位置进行下一层遍历。同时通过判断当前元素是否和上一个元素相同可去除重复子集。如果相同的话，直接跳过。
+### 思路 1：回溯算法
+
+数组的每个元素都有两个选择：选与不选。
+
+我们可以通过向当前子集数组中添加可选元素来表示选择该元素。也可以在当前递归结束之后，将之前添加的元素从当前子集数组中移除（也就是回溯）来表示不选择该元素。
+
+因为数组中可能包含重复元素，所以我们可以先将数组排序，然后在回溯时，判断当前元素是否和上一个元素相同，如果相同，则直接跳过，从而去除重复元素。
 
-## 代码
+回溯算法解决这道题的步骤如下：
+
+- 先对数组 `nums` 进行排序。
+- 从第 `0` 个位置开始，调用 `backtrack` 方法进行深度优先搜索。
+- 将当前子集数组 `sub_set` 添加到答案数组 `sub_sets` 中。
+- 然后从当前位置开始，到数组结束为止，枚举出所有可选的元素。对于每一个可选元素：
+  - 如果当前元素与上一个元素相同，则跳过当前生成的子集。
+  - 将可选元素添加到当前子集数组 `sub_set` 中。
+  - 在选择该元素的情况下，继续递归考虑下一个元素。
+  - 进行回溯，撤销选择该元素。即从当前子集数组 `sub_set` 中移除之前添加的元素。
+
+### 思路 1：回溯算法代码
 
 ```Python
 class Solution:
@@ -36,3 +64,61 @@ class Solution:
         return res
 ```
 
+### 思路 2：二进制枚举
+
+对于一个元素个数为 `n` 的集合 `nums`  来说，每一个位置上的元素都有选取和未选取两种状态。我们可以用数字 `1` 来表示选取该元素，用数字 `0` 来表示不选取该元素。
+
+那么我们就可以用一个长度为 `n` 的二进制数来表示集合 `nums` 或者表示 `nums` 的子集。其中二进制的每一位数都对应了集合中某一个元素的选取状态。对于集合中第 `i` 个元素（`i` 从 `0` 开始编号）来说，二进制对应位置上的 `1` 代表该元素被选取，`0` 代表该元素未被选取。
+
+举个例子来说明一下，比如长度为 `5` 的集合 `nums = {5, 4, 3, 2, 1}`，我们可以用一个长度为 `5` 的二进制数来表示该集合。 
+
+比如二进制数 `11111` 就表示选取集合的第 `0` 位、第 `1` 位、第 `2` 位、第 `3` 位、第 `4` 位元素，也就是集合 `{5, 4, 3, 2, 1}` ，即集合 `nums`  本身。如下表所示：
+
+| 集合 nums 对应位置（下标） |  4   |  3   |  2   |  1   |  0   |
+| :------------------------- | :--: | :--: | :--: | :--: | :--: |
+| 对应选取状态               | 选取 | 选取 | 选取 | 选取 | 选取 |
+| 二进制数对应位数           |  1   |  1   |  1   |  1   |  1   |
+
+再比如二进制数 `10101` 就表示选取集合的第 `0` 位、第 `2` 位、第 `5` 位元素，也就是集合 `{5, 3, 1}`。如下表所示：
+
+| 集合 nums 对应位置（下标） |  4   |   3    |  2   |   1    |  0   |
+| :------------------------- | :--: | :----: | :--: | :----: | :--: |
+| 对应选取状态               | 选取 | 未选取 | 选取 | 未选取 | 选取 |
+| 二进制数对应位数           |  1   |   0    |  1   |   0    |  1   |
+
+再比如二进制数 `01001` 就表示选取集合的第 `0` 位、第 `3` 位元素，也就是集合 `{5, 2}`。如下标所示：
+
+| 集合 nums 对应位置（下标） |   4    |  3   |   2    |   1    |  0   |
+| :------------------------- | :----: | :--: | :----: | :----: | :--: |
+| 对应选取状态               | 未选取 | 选取 | 未选取 | 未选取 | 选取 |
+| 二进制数对应位数           |   0    |  1   |   0    |   0    |  1   |
+
+通过上面的例子我们可以得到启发：对于长度为 `5` 的集合 `nums` 来说，我们只需要从 `00000` ~ `11111` 枚举一次（对应十进制为 $0 \sim 2^4 - 1$）即可得到长度为 `5` 的集合 `S` 的所有子集。
+
+我们将上面的例子拓展到长度为 `n` 的集合 `nums`。可以总结为：
+
+- 对于长度为 `5` 的集合 `nums` 来说，只需要枚举 $0 \sim 2^n - 1$（共 $2^n$ 种情况），即可得到所有的子集。
+
+因为数组中可能包含重复元素，所以我们可以先对数组进行排序。然后在枚举过程中，如果发现当前元素和上一个元素相同，则直接跳过当前生层的子集，从而去除重复元素。
+
+### 思路 2：二进制枚举代码
+
+```Python
+class Solution:
+    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
+        nums.sort()
+        n = len(nums)                       # n 为集合 nums 的元素个数
+        sub_sets = []                       # sub_sets 用于保存所有子集
+        for i in range(1 << n):             # 枚举 0 ~ 2^n - 1
+            sub_set = []                    # sub_set 用于保存当前子集
+            flag = True                     # flag 用于判断重复元素
+            for j in range(n):  # 枚举第 i 位元素
+                if i >> j & 1:  # 如果第 i 为元素对应二进制位为 1，则表示选取该元素
+                    if j > 0 and (i >> (j - 1) & 1) == 0 and nums[j] == nums[j - 1]:
+                        flag = False        # 如果出现重复元素，则跳过当前生成的子集
+                        break
+                    sub_set.append(nums[j]) # 将选取的元素加入到子集 sub_set 中
+            if flag:
+                sub_sets.append(sub_set)    # 将子集 sub_set 加入到所有子集数组 sub_sets 中
+        return sub_sets                     # 返回所有子集
+```
