90. Subsets II-蒲公英云

90. Subsets II

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.

Example:

Input: [1,2,2]
Output:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

方法：回溯法

避免出现重复的子集的两个要点：（1）回溯之前先排序（2）用Set记录已有的子集。

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>>  result;  //存储最终结果
        vector<int> item;            //回溯时，产生各个子集的数组
        set<vector<int>> setRes;      //去重使用的集合
        sort(nums.begin(), nums.end());  //排序
        result.push_back(item);
        generate(0, nums, item, setRes, result);
        return result;        
    }
private:
    void generate(int i,vector<int>& nums,  vector<int>& item, set<vector<int>> &setRes, vector<vector<int>> &result) 
    {
        if(i>= nums.size())
            return;
        item.push_back(nums[i]);         //添加当前元素                    
        if(setRes.find(item) == setRes.end()) //在setRes中无法找到item
        {
             setRes.insert(item);     
             result.push_back(item); 
        }
        generate(i+1, nums,item,setRes,result);  //第一次递归调用
        item.pop_back();                        //不添加当前元素
        generate(i+1, nums,item,setRes,result);  //第二次递归调用
    }      
};