90. Subsets II

 90. Subsets II

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

承 前一題 這題要求我們要改成此array不重複的元素的子集合，解法的思維跟上題差不多。

而這次的排序就非常重要了， 可以將重複的元素集中在一起。

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
       
       vector<vector<int>> ans;
       vector<int> sub{};
       
       //先將空集合加入
       ans.push_back(sub);
       //做排序
       sort(nums.begin(), nums.end());
       subsetsDFS(nums, sub, 0, ans);
       return ans; 
    }
    
    void subsetsDFS(const vector<int>& nums, vector<int> &sub, int start, vector<vector<int>> &output)
    {
        for(int i = start; i < nums.size(); i++)
        {
           //將重複的元素過濾掉    
           if(i > start && nums[i] == nums[i -1]) continue;
           
           sub.push_back(nums[i]);    
           output.push_back(sub);
           subsetsDFS(nums, sub, i+1, output);
           //找過的給清掉
           sub.pop_back();
        }
    }
};