[leetcode] Subsets II

Subsets II

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If nums = `[1,2,2]`, a solution is:

```[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]```
```//本题重点是判断何时会出现duplicate的情况
//让结果decrease排列很简单，只要sort nums就好
//结果中出现duplicate是因为前一个相同的数字没有取，但下一个取了
//比如数列 x1 x2 x3 y1 z1
//其中x1 = x2 = x3 != y1 != z1
//如果x1没有取，那么x2也不能取，x3也不能取，否则会出现重复结果。
//如果x1取了，x2可以取也可以不取，如果x2没有取，那么x3也不能取。
//在代码中我们用isLastChosen来表示前一个元素取没取。
//时间复杂度o(2^n)
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<vector<int>> re;
vector<int> thisRe;
if(nums.empty() == true){
return re;
}
sort(nums.begin(), nums.end());
_subsetWithDup(re, thisRe, 0, nums, false);
return re;
}

void _subsetWithDup(vector<vector<int>> &re, vector<int> &thisRe, int index, vector<int>& nums, bool isLastChosen){
size_t len = nums.size();
if(index == len){
//finish
re.push_back(thisRe);
return ;
}
if(index == 0 || nums[index] != nums[index - 1]){
thisRe.push_back(nums[index]);
_subsetWithDup(re, thisRe, index + 1, nums, true);
thisRe.pop_back();
_subsetWithDup(re, thisRe, index + 1, nums, false);
}
else{
//dup, nums[index] == nums[index - 1]
if(isLastChosen == true){
thisRe.push_back(nums[index]);
_subsetWithDup(re, thisRe, index + 1, nums, true);
thisRe.pop_back();
}
_subsetWithDup(re, thisRe, index + 1, nums, false);
}
}
};
```

This site uses Akismet to reduce spam. Learn how your comment data is processed.