55
66##题目大意
77
8- 给定一个整数数组` nums ` ，其中可能包含重复元素。
8+ ** 描述 ** ： 给定一个整数数组` nums ` ，其中可能包含重复元素。
99
10- 要求 ：返回该数组所有可能的子集（幂集）。
10+ ** 要求 ** ：返回该数组所有可能的子集（幂集）。
1111
12- 注意：解集不能包含重复的子集。返回的解集中，子集可以按任意顺序排列。
12+ ** 说明** ：
13+
14+ - 解集不能包含重复的子集。返回的解集中，子集可以按任意顺序排列。
15+ - $1 \le nums.length \le 10$。
16+ - $-10 \le nums[ i] \le 10$。
17+
18+ ** 示例** ：
19+
20+ ``` Python
21+ 输入nums= [1 ,2 ,2 ]
22+ 输出[[],[1 ],[1 ,2 ],[1 ,2 ,2 ],[2 ],[2 ,2 ]]
23+ ```
1324
1425##解题思路
1526
16- 先对数组` nums ` 进行排序。回溯的时候，每次遍历从当前位置的下一个位置进行下一层遍历。同时通过判断当前元素是否和上一个元素相同可去除重复子集。如果相同的话，直接跳过。
27+ ###思路 1：回溯算法
28+
29+ 数组的每个元素都有两个选择：选与不选。
30+
31+ 我们可以通过向当前子集数组中添加可选元素来表示选择该元素。也可以在当前递归结束之后，将之前添加的元素从当前子集数组中移除（也就是回溯）来表示不选择该元素。
32+
33+ 因为数组中可能包含重复元素，所以我们可以先将数组排序，然后在回溯时，判断当前元素是否和上一个元素相同，如果相同，则直接跳过，从而去除重复元素。
1734
18- ##代码
35+ 回溯算法解决这道题的步骤如下：
36+
37+ - 先对数组` nums ` 进行排序。
38+ - 从第` 0 ` 个位置开始，调用` backtrack ` 方法进行深度优先搜索。
39+ - 将当前子集数组` sub_set ` 添加到答案数组` sub_sets ` 中。
40+ - 然后从当前位置开始，到数组结束为止，枚举出所有可选的元素。对于每一个可选元素：
41+ - 如果当前元素与上一个元素相同，则跳过当前生成的子集。
42+ - 将可选元素添加到当前子集数组` sub_set ` 中。
43+ - 在选择该元素的情况下，继续递归考虑下一个元素。
44+ - 进行回溯，撤销选择该元素。即从当前子集数组` sub_set ` 中移除之前添加的元素。
45+
46+ ###思路 1：回溯算法代码
1947
2048``` Python
2149class Solution :
@@ -36,3 +64,61 @@ class Solution:
3664return res
3765```
3866
67+ ###思路 2：二进制枚举
68+
69+ 对于一个元素个数为` n ` 的集合` nums ` 来说，每一个位置上的元素都有选取和未选取两种状态。我们可以用数字` 1 ` 来表示选取该元素，用数字` 0 ` 来表示不选取该元素。
70+
71+ 那么我们就可以用一个长度为` n ` 的二进制数来表示集合` nums ` 或者表示` nums ` 的子集。其中二进制的每一位数都对应了集合中某一个元素的选取状态。对于集合中第` i ` 个元素（` i ` 从` 0 ` 开始编号）来说，二进制对应位置上的` 1 ` 代表该元素被选取，` 0 ` 代表该元素未被选取。
72+
73+ 举个例子来说明一下，比如长度为` 5 ` 的集合` nums = {5, 4, 3, 2, 1} ` ，我们可以用一个长度为` 5 ` 的二进制数来表示该集合。
74+
75+ 比如二进制数` 11111 ` 就表示选取集合的第` 0 ` 位、第` 1 ` 位、第` 2 ` 位、第` 3 ` 位、第` 4 ` 位元素，也就是集合` {5, 4, 3, 2, 1} ` ，即集合` nums ` 本身。如下表所示：
76+
77+ | 集合 nums 对应位置（下标）| 4| 3| 2| 1| 0|
78+ | :-------------------------| :--:| :--:| :--:| :--:| :--:|
79+ | 对应选取状态| 选取| 选取| 选取| 选取| 选取|
80+ | 二进制数对应位数| 1| 1| 1| 1| 1|
81+
82+ 再比如二进制数` 10101 ` 就表示选取集合的第` 0 ` 位、第` 2 ` 位、第` 5 ` 位元素，也就是集合` {5, 3, 1} ` 。如下表所示：
83+
84+ | 集合 nums 对应位置（下标）| 4| 3| 2| 1| 0|
85+ | :-------------------------| :--:| :----:| :--:| :----:| :--:|
86+ | 对应选取状态| 选取| 未选取| 选取| 未选取| 选取|
87+ | 二进制数对应位数| 1| 0| 1| 0| 1|
88+
89+ 再比如二进制数` 01001 ` 就表示选取集合的第` 0 ` 位、第` 3 ` 位元素，也就是集合` {5, 2} ` 。如下标所示：
90+
91+ | 集合 nums 对应位置（下标）| 4| 3| 2| 1| 0|
92+ | :-------------------------| :----:| :--:| :----:| :----:| :--:|
93+ | 对应选取状态| 未选取| 选取| 未选取| 未选取| 选取|
94+ | 二进制数对应位数| 0| 1| 0| 0| 1|
95+
96+ 通过上面的例子我们可以得到启发：对于长度为` 5 ` 的集合` nums ` 来说，我们只需要从` 00000 ` ~` 11111 ` 枚举一次（对应十进制为 $0 \sim 2^4 - 1$）即可得到长度为` 5 ` 的集合` S ` 的所有子集。
97+
98+ 我们将上面的例子拓展到长度为` n ` 的集合` nums ` 。可以总结为：
99+
100+ - 对于长度为` 5 ` 的集合` nums ` 来说，只需要枚举 $0 \sim 2^n - 1$（共 $2^n$ 种情况），即可得到所有的子集。
101+
102+ 因为数组中可能包含重复元素，所以我们可以先对数组进行排序。然后在枚举过程中，如果发现当前元素和上一个元素相同，则直接跳过当前生层的子集，从而去除重复元素。
103+
104+ ###思路 2：二进制枚举代码
105+
106+ ``` Python
107+ class Solution :
108+ def subsetsWithDup (self nums : List[int ]) -> List[List[int ]]:
109+ nums.sort()
110+ n= len (nums)# n 为集合 nums 的元素个数
111+ sub_sets= []# sub_sets 用于保存所有子集
112+ for iin range (1 << n):# 枚举 0 ~ 2^n - 1
113+ sub_set= []# sub_set 用于保存当前子集
114+ flag= True # flag 用于判断重复元素
115+ for jin range (n):# 枚举第 i 位元素
116+ if i>> j& 1 :# 如果第 i 为元素对应二进制位为 1，则表示选取该元素
117+ if j> 0 and (i>> (j- 1 )& 1 )== 0 and nums[j]== nums[j- 1 ]:
118+ flag= False # 如果出现重复元素，则跳过当前生成的子集
119+ break
120+ sub_set.append(nums[j])# 将选取的元素加入到子集 sub_set 中
121+ if flag:
122+ sub_sets.append(sub_set)# 将子集 sub_set 加入到所有子集数组 sub_sets 中
123+ return sub_sets# 返回所有子集
124+ ```
