Subsets II

Desicription

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.

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

1
2
3
4
5
6
7
8
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<vector<int>> res = {{}};
sort(nums.begin(), nums.end());
for(int i = 0; i < nums.size();) {
int repeat_cnt = 0;
while(repeat_cnt + i < nums.size() && nums[repeat_cnt+i] == nums[i])
repeat_cnt++;
int res_size = res.size();
for(int j = 0; j < res_size; j++) {
vector<int> currency = res[j];
for(int k = 0; k < repeat_cnt; k++){
currency.push_back(nums[i]);
res.push_back(currency);
}
}
i += repeat_cnt;
}
return res;
}
};