Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:
Input: [1,2,2]
Output:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
AC代碼
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
if (nums.empty()) return {};
sort(nums.begin(), nums.end());
vector<vector<int>> res{{}};
vector<int> t;
int k = 0;
for (int i = 0; i < nums.size(); ++i) {
int size = res.size();
int j = 0;
if (i > 0 && nums[i] == nums[i - 1]) j = res.size() - k;
k = 0;
for (; j < size; j++) {
res.push_back(res[j]);
res.back().push_back(nums[i]);
k++;
}
}
return res;
}
};
總結(jié)
基于沒有重復(fù)值求子集的一個(gè)方法：（78題中有寫）
1、創(chuàng)建一個(gè)只有空集的vector<vecor<int>> res
2眯亦、nums有n個(gè)數(shù)咳蔚，做n次循環(huán)
3、對(duì)每次循環(huán)搔驼，復(fù)制已在res里的vecor<int>,在末尾添加nums[i]后作為新元素添加到res
如果有重復(fù)值谈火，上述第3步驟就要改，不能復(fù)制res中所有已有的元素然后添加當(dāng)前nums[i]舌涨，只能在上次循環(huán)中新加入的vector<int>后面添加nums[i]糯耍，用k記錄上次循環(huán)添加了多少新內(nèi)容，然后用res.size()-k得到正確的起始下標(biāo)
