方寸心思

本文由抱雪(hugsnow)原创，转载请注明来源 http://www.luoxf.net/

 1 #include <algorithm>
 2 #include <vector>
 3 #include <iterator>
 4 #include <iostream>
 5 using namespace std;
 6 /**
 7  * 分析：组合无序，所以不妨设降序排列
 8  * 第一个解是[n,n-1,...,n-r+1]
 9  * 解的条件是位置i上的元素A[i]应该满足
10  * i+A[i]>=r
11  * 回溯法：对最后一个元素减一
12  * 如果满足条件则得到一个新解
13  * 如果不满足，一直向前回溯到该位满足为止
14  * 然后把满足的那位后面的依次等于前面减一
15  * 从而得到一组新解,然后继续
16  * 如果已经回溯到第一位仍不满足
17  * 则所有解都已经找到，终止
18  */
19 vector <vector <int> > comb(int n,int r){
20     vector <vector <int> > vv;
21     vector <int> tmp(r);
22     int i;
23     bool f=false;
24     for(i=0;i<r;i++)tmp[i]=n-i;
25     vv.push_back(tmp);
26     while(true){
27         tmp[r-1]--;
28         for(i=r-1;i>=0;i--){
29             if(tmp[i]+i>=r)
30                 break;
31             else{
32                 if(i==0){
33                     f=true;
34                     break;
35                 }
36                 tmp[i-1]--;
37                 if(tmp[i-1]+i-1>=r){
38                     for (int j=i; j < r; j++) {
39                         tmp[j]=tmp[j-1]-1;
40                     }
41                 }
42             }
43         }
44         if(f)break;
45         vv.push_back(tmp);
46     }
47     return vv;
48 }
49 

标签：原创