1、



Subsets

Given a set of distinct integers, 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,3], a solution is:

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

分析：想到的方法是首先进行排序，从头到尾一次选择要不要该元素。能够递归实现。例如以下代码。

class Solution {public:    vector
     
      
        >*  v;    vector
       
        
          > subsets(vector
         
           &S) {            v = new vector
          
           
             >(); //先排序 sort(S.begin(),S.end()); vector
            
              res; generate(res, S, 0); return *v; } //对每个元素有放与不放两种选择 void generate(vector
             
               res, vector
              
                &S, int i) { if(i == S.size()) { v->push_back(res); return; } else { generate(res, S, i+1);//不放当前元素 res.push_back(S[i]); //放入当前元素 generate(res, S, i+1); } }};
              
             
            
           
          
         
        
       
      
     

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

分析：此题和上题类似，就是有了反复元素，想法也是先进行排序，排序后，从头到尾遍历，记录每一个元素的个数，每一个子集中有0-i个指定元素（一共i个）,代码例如以下：

class Solution {public:    vector
     
      
        >*  v;    vector
       
        
          > subsetsWithDup(vector
         
           &S) {            v = new vector
          
           
             >(); //先排序 sort(S.begin(),S.end()); vector
            
              res; generate(res, S, 0,0,0); return *v; } //pre： 排序后前一个元素 num： 前一个元素出现的次数 void generate(vector
             
               res, vector
              
                &S, int i,int pre,int num) { if(i == S.size()) { v->push_back(res); for(int j=1; j<=num; ++j){ res.push_back(pre); //放入之前元素 v->push_back(res); } return; } else if(pre != S[i] || num < 1 ) //与之前元素不同或者是首次 { if(num < 1){ generate(res,S,i+1,S[i],1); }else{ generate(res, S, i+1,S[i],1);//放入0个元素 for(int j=1; j<=num; ++j){ res.push_back(pre); generate(res, S, i+1,S[i],1);//放入i个元素后从当前位置開始 } } }else{ pre = S[i]; generate(res, S, i+1,pre,num+1); } }};
              
             
            
           
          
         
        
       
      
     

版权声明：本文博客原创文章，博客，未经同意，不得转载。