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 =
If nums =
[1,2,2]
, a solution is:[ [2], [1], [1,2,2], [2,2], [1,2], [] ]
class Solution { public: vector<vector<int>> subsetsWithDup(vector<int>& nums) { vector<vector<int>> res(1); sort(nums.begin(), nums.end()); int lastSize; for(int i=0;i<nums.size();i++) { int start = 0; int size = res.size(); if(i>0 && nums[i] == nums[i-1]) { start = size - lastSize; } for(int j=start;j<size;j++) { vector<int> tmp = res[j]; tmp.push_back(nums[i]); res.push_back(tmp); } lastSize = size - start; } return res; } };