90. Subsets II（子集 II）
- 1. 题目描述
- 2. 跳过重复子集（Jump Duplicate Subsets over）
-
- 3.1 解题思路
- 3.2 实例代码
- 3. 递归 & 迭代 & 位操作（Recursion & Iteration & Bit Manipulation）
-
- 3.1 解题思路
- 3.2 实例代码
- 4. 参考资料
1. 题目描述
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
题目链接：中文题目；英文题目
2. 跳过重复子集（Jump Duplicate Subsets over）
3.1 解题思路
首先这题和78. Subsets（子集）的基本思路是一样的，之前的三种方法同样适用，只需要添加了Hash Table把重复元素去除就行了，只是还需要先排序，否则部分重复的子集是无法被区分的：[1,2] 和 [2,1]。至于为什么要排序，我们来看看下面两个例子：
例1：[1,2,2]
例2：[2,1,2]
我们以之前的迭代方法来进行求解：
例1：[] -> [], [1] -> [], [1], [2], [1,2] -> [], [1], [2], [1,2], [2], [1,2], [2,2], [1,2,2]
例2：[] -> [], [2] -> [], [2], [1], [2,1] -> [], [2], [1], [2,1], [2], [2,2], [1,2], [2,1,2]
例2中[1,2]和[2,1]是一样的子集，所以必须先排序才能求解；
所以原来三种方法的Hash Table更新版的思路这里就不再赘述了，各位童鞋可以参考：78. Subsets（子集）三种解法（C++ & 注释）。这里主要讲解一下不使用Hash Table的迭代方法，因而 3. 递归 & 迭代 & 位操作（Recursion & Iteration & Bit Manipulation）章节 包含三种方法对应的Hash Table更新版，大家可以到对应章节查看相关代码。
通过上面例1的分析，我们发现排序后，相同数字生成的子集无需生成之前同数字生成的子集，比如例子1中第一个2和[], [1]生成[2], [1,2]，那么第二个2就不需要再和[],[1]生成子集，只是需要和第一个2生成的新子集生成子集即可，即[2], [1,2] -> [2,2], [1,2,2]。
至此我们得到了最为关键的思路：不同数字从头开始生成子集，相同数字跳过上一个同数字生成的子集，再生成相应的子集。具体的流程如下图所示：
3.2 实例代码
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<vector<int>> ans(1, vector<int>());
sort(nums.begin(), nums.end());
int s = 0;
for (int i = 0; i < nums.size(); i++) {
if (!i || nums[i] != nums[i - 1]) s = 0; // 不同数字从头开始生成子集
for (int e = ans.size(); s < e; s++) {
vector<int> temp = ans[s];
temp.push_back(nums[i]);
ans.push_back(temp);
}
}
return ans;
}
};
3. 递归 & 迭代 & 位操作（Recursion & Iteration & Bit Manipulation）
3.1 解题思路
这部分思路请参考：78. Subsets（子集）三种解法（C++ & 注释），有任何问题欢迎留言哒~
3.2 实例代码
3.2.1 递归
class Solution {
vector<vector<int>> ans;
set<vector<int>> ansTemp;
vector<int> temp;
void recursionMethod(vector<int>& nums, int idx, int k) {
if (k == temp.size()) { ansTemp.insert(temp); return; }
for (int i = idx; i < nums.size(); i++) {
temp.push_back(nums[i]);
recursionMethod(nums, i + 1, k);
temp.pop_back();
}
}
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end());
for (int i = 0; i <= nums.size(); i++) recursionMethod(nums, 0, i);
for (const vector<int>& v : ansTemp) ans.push_back(v);
return ans;
}
};
3.3.2 迭代
// 迭代不能先把子集加入到Set中，因为需要重复利用ans中的子集生成新子集，没办法用序号来访问set，即set[number]
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<vector<int>> ans(1, vector<int>());
set<vector<int>> ansTemp;
vector<int> temp;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++) {
int len = ans.size();
for (int j = 0; j < len; j++) {
vector<int> temp = ans[j];
temp.push_back(nums[i]);
ans.push_back(temp);
}
}
for (vector<int>& v : ans) ansTemp.insert(v);
ans.clear();
for (const vector<int>& v : ansTemp) ans.push_back(v);
return ans;
}
};
3.3.3 位操作
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<vector<int>> ans;
set<vector<int>> ansTemp;
int len = nums.size(), bitMax = 1;
sort(nums.begin(), nums.end());
for (int i = 0; i < len - 1; i++) bitMax = (bitMax << 1) + 1; // 生成nums所表示的最大二进制数
for (int bitMask = 0; bitMask <= (len ? bitMax : 0); bitMask++) {
int idx = len - 1, bitManipulation = bitMask;
vector<int> temp;
// 按照二进制1和0的规律，生成相应子集
while (bitManipulation) {
if ((bitManipulation & 1) == 1) temp.push_back(nums[idx]);
idx--;
bitManipulation >>= 1;
}
ansTemp.insert(temp);
}
for (const vector<int>& v : ansTemp) ans.push_back(v);
return ans;
}
};
4. 参考资料
- C++ solution and explanation
