<p>Given an integer array <code>nums</code> that may contain duplicates, return <em>all possible</em> <span data-keyword="subset"><em>subsets</em></span><em> (the power set)</em>.</p>

<p>The solution set <strong>must not</strong> contain duplicate subsets. Return the solution in <strong>any order</strong>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> nums = [1,2,2]
<strong>Output:</strong> [[],[1],[1,2],[1,2,2],[2],[2,2]]
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> nums = [0]
<strong>Output:</strong> [[],[0]]
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10</code></li>
	<li><code>-10 &lt;= nums[i] &lt;= 10</code></li>
</ul>

class Solution {
public:

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>>ans;
        vector<int> cur;
        int n = nums.size();
        vector<int>vis(n,0);
        map<vector<int>,int>man;
        int ind =0;
        ans.push_back(cur);
        func(ans, nums, cur, ind, vis, man);
        return ans;
    }
    void func(vector<vector<int>>&ans, vector<int>nums, vector<int>cur, int ind,vector<int>vis, map<vector<int>,int>&man){
        int n = nums.size();
        map<int, int> ma;
        for(int i = ind; i<n; i++){  
            if(ma.find(nums[i])==ma.end()){
                if(vis[i]==0){
                    ma[nums[i]]=1;
                    vector<int>curr = cur;
                    curr.push_back(nums[i]);
                    sort(curr.begin(),curr.end());
                    vis[i]=1; 
                    if(man.find(curr)==man.end()){    
                        man[curr]=1;
                        func(ans, nums, curr, ind+1, vis, man);   
                        ans.push_back(curr);
                    }   
                    
                }
            }
            else{
                vis[i]=1;
            }  

            
        }
        return;
    }
};
12598