题目

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

思路

和78.Subsets的唯一区别就是添加了两行去重的代码。

代码

    /**------------------------------------
    *   日期：2015-03-01
    *   作者：SJF0115
    *   题目: 90.Subsets II
    *   网址：https://oj.leetcode.com/problems/subsets-ii/
    *   结果：AC
    *   来源：LeetCode
    *   博客：
    ---------------------------------------**/
    #include 
   
     #include 
    
      #include 
     
       using namespace std; class Solution { public: vector
      
        > subsetsWithDup(vector
       
         &S) { int size = S.size(); vector
        
          > result; vector
         
           path; // 排序 sort(S.begin(),S.end()); // 空集 result.push_back(path); // 其他子集 for(int i = 1;i <= size;++i){ DFS(S,size,i,0,path,result); }//for return result; } private: // s源数据集 n源数据个数 k子集长度 index为第index个元素 path路径 result最终结果 void DFS(vector
          
            &s,int n,int k,int index,vector
           
             &path,vector
            
              > &result){ // 一个子集 if(path.size() == k){ result.push_back(path); return; }//if for(int i = index;i < n;++i){ // 去重 if(i != index && s[i] == s[i-1]){ continue; }//if path.push_back(s[i]); DFS(s,n,k,i+1,path,result); path.pop_back(); }//for } }; int main(){ Solution s; vector
             
               num = {1,2,2}; vector
              
                > result = s.subsetsWithDup(num); // 输出 for(int i = 0;i < result.size();++i){ for(int j = 0;j < result[i].size();++j){ cout<