题目描述
给你一个整数数组 nums ,其中可能包含重复元素,请你返回该数组所有可能的子集(幂集)。
解集不能包含重复的子集。返回的解集中,子集可以按任意顺序排列。
样例
输入:nums = [1,2,2]
输出:[[],[1],[1,2],[1,2,2],[2],[2,2]]
类似题
https://leetcode-cn.com/problems/subsets/
也是求子集,但是它的nums没有重复元素。
https://leetcode-cn.com/problems/subsets/solution/zi-ji-by-leetcode-solution/
算法1
递归
class Solution {
public:
vector<vector<int>> ans;
vector<int> tmp;
void dfs(int cur, vector<int>& nums){
if(cur == nums.size()){
ans.push_back(tmp);
return ;
}
tmp.push_back(nums[cur]);
dfs(cur+1, nums);
tmp.pop_back();
dfs(cur+1, nums);
}
vector<vector<int>> subsets(vector<int>& nums) {
dfs(0, nums);
return ans;
}
};
算法2
迭代+位运算
参考
https://leetcode-cn.com/problems/subsets/solution/zi-ji-by-leetcode-solution/
class Solution {
public:
vector<int> t;
vector<vector<int>> ans;
vector<vector<int>> subsets(vector<int>& nums) {
int n = nums.size();
for(int mask = 0; mask < (1 << n); mask++){
t.clear();
for(int i = 0; i < n; i++){
if(mask & (1 << i)){
t.push_back(nums[i]);
}
}
ans.push_back(t);
}
return ans;
}
};
回到本题
考虑数组 [1,2,2][1,2,2][1,2,2],选择前两个数,或者第一、三个数,都会得到相同的子集。
也就是说,对于当前选择的数 xxx,若前面有与其相同的数 yyy,且没有选择 yyy,此时包含 xxx 的子集,必然会出现在包含 yyy 的所有子集中。
我们可以通过判断这种情况,来避免生成重复的子集。代码实现时,可以先将数组排序;迭代时,若发现没有选择上一个数,且当前数字与上一个数相同,则可以跳过当前生成的子集。
算法1
递归
class Solution {
public:
vector<vector<int>> ans;
vector<int> tmp;
void dfs(bool preChoose, int cur, vector<int>& nums){
if(cur == nums.size()){
ans.push_back(tmp);
return ;
}
dfs(false, cur+1, nums);
if(!preChoose && cur > 0 && nums[cur] == nums[cur-1]){
return;
}
tmp.push_back(nums[cur]);
dfs(true, cur+1, nums);
tmp.pop_back();
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end());
dfs(false, 0, nums);
return ans;
}
};
算法2
迭代+位运算
参考
https://leetcode-cn.com/problems/subsets-ii/solution/zi-ji-ii-by-leetcode-solution-7inq/
如何判断重复数没看懂,位运算不熟悉
class Solution {
public:
vector<vector<int>> ans;
vector<int> tmp;
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end());
int n = nums.size();
for(int mask = 0; mask < (1 << n); mask++){
tmp.clear();
bool flag = true;
for(int i = 0; i < n; i++){
if(mask & (1 << i)){
if(i > 0 && (mask >> (i - 1) & 1) == 0 && nums[i] == nums[i-1]){
flag = false;
break;
}
tmp.push_back(nums[i]);
}
}
if(flag) ans.push_back(tmp);
}
return ans;
}
};