题目描述

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

样例

输入: [1,2,2]
输出:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

C++ 代码

class Solution {
public:
    vector<vector<int>> result;
    vector<int> list;//当前装入的元素

    void dfs(vector<int>& nums ,int pos,vector<int>& visited)
    {
        if(pos==nums.size())
        {
            result.push_back(list);//当前list装入vector,
            return ;
        }
        //规定前面的选了，后面的可以选或不选
        //前面的没选，后面的则不选 
        //所以后面的元素都可以不选，而前面的元素需要根据某些情况来定选不选
        if(  pos==0 ||  nums[pos-1]!=nums[pos]  
            || visited[pos-1]==1     )//当前和前一个元素相同，且前一个元素已经选了
        {
            list.push_back(nums[pos]);
            visited[pos]=1;
            dfs(nums,pos+1,visited);//选择当前元素后进入，下一个元素
            visited[pos]=0;
            list.pop_back();
        }

        dfs(nums,pos+1,visited);//不选后面的元素

    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(),nums.end());//先排序
        vector<int> visited(nums.size(),0);//表示之前的元素是否选择了
        dfs(nums,0,visited);
        return result;
    }
};