[LeetCode]90.Subsets II-白红宇

题目

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

[]

]

思路

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

代码

/**------------------------------------    *   日期：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<
                     
                      <<" "; }//for cout<

运行时间

这里写图片描述