Combination 组合

admin1

1. template <typename T>class Combination
   
2. {
   
3. public:   
   
4.         typedef vector<T> Sequence;
   
5. 
   
6. public:   
   
7.         // 从序列sourceSeq中选取m个元素的组合   
   
8.         vector<Sequence> combination(const Sequence &sourceSeq, int m)   
   
9.         {   
   
10.                 vector<Sequence> totalSeq;
    
11.                 if (m <= 0 || m > sourceSeq.size())            
    
12.                         return totalSeq;
    
13.       
    
14.                 Sequence targetSeq;        
    
15.                 combination(sourceSeq, m, 0, targetSeq, totalSeq);        
    
16.                 return totalSeq;   
    
17.         }
    
18. 
    
19. private:   
    
20.         void combination(const Sequence &sourceSeq, int m, int cur, Sequence &targetSeq, vector<Sequence> &totalSeq)   
    
21.         {        
    
22.                 if (targetSeq.size() == m)        
    
23.                 {            
    
24.                         totalSeq.push_back(targetSeq);            
    
25.                         return;        
    
26.                 }
    
27. 
    
28.                 for (int i = cur; i < sourceSeq.size(); i++)        
    
29.                 {            
    
30.                         // 做出选择            
    
31.                         targetSeq.push_back(sourceSeq[i]);            
    
32.                         // 递归调用            
    
33.                         combination(sourceSeq, m, i + 1, targetSeq, totalSeq);            
    
34.                         // 撤销选择            
    
35.                         targetSeq.pop_back();        
    
36.                 }   
    
37.         }
    
38. };

复制代码

admin1

1. class Solution {
   
2. public:
   
3.         void getsubset(int start, int end,int k, vector<double> &temp, vector<vector<double>> &result,vector<double> &S)
   
4.         {
   
5.                 if(temp.size() == k)
   
6.                 {
   
7.                         result.push_back(temp);
   
8.                         return;
   
9.                 }
   
10.                 for(int i = start; i <=end; i++)
    
11.                 {
    
12.                         temp.push_back(S[i]);
    
13.                         getsubset(i+1,end,k,temp,result,S);
    
14.                         temp.pop_back();
    
15.                 }
    
16.         }
    
17.         vector<vector<double> > subsets(vector<double> &S) {
    
18.                 vector<vector<double>> result;
    
19.                 vector<double> temp;
    
20.                 int num = (int)S.size();
    
21.                 sort(S.begin(), S.end());
    
22.                 for(int i = 1; i <= num; i++)
    
23.                 {
    
24.                         getsubset(0,num-1,i,temp,result,S);
    
25.                 }
    
26.                 return result;
    
27.         }
    
28. };
    

复制代码