本文共 1043 字，大约阅读时间需要 3 分钟。

Given a collection of integers that might contain duplicates, S, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If S = [1,2,2], a solution is:

[  [2],  [1],  [1,2,2],  [2,2],  [1,2],  []]

有图为证：

class Solution {public:    void subReII(vector
   
    
      >& re, vector
     
       &s,int j)	{		if(s.size() <= j)			return;		int size_ = re.size();		int k = j + 1;		//get the 重复区间,k是下个不重复的位置。		while(k < s.size() && s[k] == s[k - 1]) k++;		for(int i = 0; i < size_; ++i)		{			int cur = j;			vector
      
        copy(re[i]);			//将重复的元素从 1 个到所有依次加入进去。			while(cur < k)			{				copy.push_back(s[j]);			    re.push_back(copy);				++cur;			}		}		//skip the 重复区间，到下一个不是重复的位置，递归。		subReII(re, s, k);	}	vector
       
        
          > subsetsWithDup(vector
         
           &S) { vector
          
           
             > re; vector
            
              sol; sort(S.begin(),S.end()); re.push_back(sol); subReII(re, S, 0); return re; }};