題目鏈接
tag:
- Medium效拭；
question：
??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],
[]
]
思路：
??這道子集合二是之前那道 Subsets 子集合 的延伸攻泼，這次輸入數(shù)組允許有重復項雪位，其他條件都不變，只需要在之前那道題解法的基礎上稍加改動便可以做出來抑胎，我們先來看非遞歸解法燥滑，拿題目中的例子[1 2 2]來分析，根據(jù)之前 Subsets 子集合 里的分析可知阿逃，當處理到第一個2時铭拧，此時的子集合為[], [1], [2], [1, 2]，而這時再處理第二個2時恃锉，如果在[]和[1]后直接加2會產生重復搀菩，所以只能在上一個循環(huán)生成的后兩個子集合后面加2，發(fā)現(xiàn)了這一點破托，題目就可以做了肪跋，我們用last來記錄上一個處理的數(shù)字，然后判定當前的數(shù)字和上面的是否相同土砂，若不同州既，則循環(huán)還是從0到當前子集的個數(shù)，若相同萝映，則新子集個數(shù)減去之前循環(huán)時子集的個數(shù)當做起點來循環(huán)吴叶，這樣就不會產生重復了，代碼如下：
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int> &S) {
if (S.empty()) return {};
vector<vector<int>> res(1);
sort(S.begin(), S.end());
int size = 1, last = S[0];
for (int i = 0; i < S.size(); ++i) {
if (last != S[i]) {
last = S[i];
size = res.size();
}
int newSize = res.size();
for (int j = newSize - size; j < newSize; ++j) {
res.push_back(res[j]);
res.back().push_back(S[i]);
}
}
return res;
}
};
