欢迎访问LeetCode题解合集
题目描述
给定一个可能包含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。
说明:解集不能包含重复的子集。
示例:
输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
题解:
法一:
回溯。
参考 子集 一题,唯一的区别是此题有重复元素,关键是怎么去重?
首先将 nums
排序,相同的元素紧挨着,方便处理。
其实去重也很简单,核心思想就是:同一层的相同元素需要跳过 。
反映到到代码上就是:
for ( int i = p; i < nums.size(); ++i ) {
if ( i > p && nums[i] == nums[i - 1] ) continue;
....
}
这句话的意思是:同一层的相同元素只用第一个就可以了,而在同一个分支上,相同元素可以继续使用。
与下面这个代码区分开:
for ( int i = p; i < nums.size(); ++i ) {
if ( i && nums[i] == nums[i - 1] ) continue;
....
}
这份代码把同一个分支上的相同元素忽略掉了。
时间复杂度:$O(n*2^n)$
额外空间复杂度:$O(n)$
class Solution {
public:
vector<vector<int>> ret;
vector<int> path;
void dfs( int p, const vector<int>& nums ) {
ret.emplace_back( path );
for ( int i = p; i < nums.size(); ++i ) {
if ( i > p && nums[i] == nums[i - 1] ) continue;
path.emplace_back( nums[i] );
dfs( i + 1, nums );
path.pop_back();
}
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort( nums.begin(), nums.end() );
if ( !nums.size() ) return {};
dfs( 0, nums );
return ret;
}
};
/*
时间:0ms,击败:100.00%
内存:7.5MB,击败:58.37%
*/
法二:
二进制枚举子集。
如果 nums
没有重复元素,二进制枚举子集就非常容易,但是出现重复元素该怎么处理呢?
举个例子,nums = [2, 2, 2]
,假设枚举 [2, 2]
这个子集,有三种情况:
1. 1 1 0
2. 1 0 1
3. 0 1 1
可以看到,1 1 0
是第一个找到的 [2, 2]
子集,而剩下的两个是重复结果,下面来考虑去掉重复结果:
我们考虑非第 0
位为 1
的前一位元素 :
1. 1 1 0 ---> 1
2. 1 0 1 ---> 0
3. 0 1 1 ---> 0
这就出现了一个规律,非第零位为 1
的前一位为 0
表示重复结果,于是就可以在基础的二进制枚举子集上稍微改动一下:
class Solution {
public:
vector<vector<int>> ret;
vector<int> path;
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
if ( !nums.size() ) return {};
sort( nums.begin(), nums.end() );
int n = nums.size();
bool flag;
for ( int i = 0; i < 1 << n; ++i ) {
path.clear();
flag = true;
for ( int j = 0; j < n; ++j ) {
if ( i >> j & 1 ) {
if ( j && nums[j] == nums[j - 1] && !(i >> (j - 1) & 1) ) {
flag = false;
break;
} else path.emplace_back( nums[j] );
}
}
if ( flag ) ret.emplace_back( path );
}
return ret;
}
};
/*
时间:0ms,击败:100.00%
内存:7.3MB,击败:87.24%
*/
法二那边感觉写反了,例子那边[2,2,2]的情况,011(二进制)会是第一个子集