Leetcode 90. Subsets II

90. Subsets II

Total Accepted: 74830
Total Submissions: 236128
Difficulty: Medium

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

Note: 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],
  []
]

思路：做法和Leetcode 78. Subsets类似，只是多了重复元素，所以只要去除重复元素的情况就可以。

代码：

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