90. Subsets II
Description
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],
[]
]
Analysis
这道题和subsets I如出一辙，不过区别在于，此题中可能含有重复元素，所以在回溯过程中需要判断出现了重复的元素，最简单的方法就是先让list有序，之后在backtracking函数中加入if判断即可，代码如下:
code
class Solution {
private:
void backtracking(vector<vector<int>> & res,vector<int> & temp,vector<int> & nums,int start){
res.push_back(temp);
for(int i=start;i<nums.size();++i){
if(i>start && nums[i]==nums[i-1]) continue;//discard the duplicates
temp.push_back(nums[i]);
backtracking(res,temp,nums,i+1);
temp.pop_back();
}
}
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<vector<int>> res;
vector<int> temp;
sort(nums.begin(),nums.end());
backtracking(res,temp,nums,0);
return res;
}
};