递归实现指数型枚举

递归的思想是：将大的问题转化为小问题。

如：

从1-n这n个数中选任意的数的，输出所有可能的方案数。

递归解决问题：

  1 #include <vector>
  2 #include <iostream>
  3 using namespace std;
  4 int n;
  5 vector<int> chosen;
  6 void calc(int x){
  7     if(x == n + 1)
  8     {
  9         for(auto i: chosen)
 10             cout << i << " ";
 11         cout << endl;
 12         return;
 13     }
 14     calc(x+1);//不选x
 15     chosen.push_back(x);//选x
 16     calc(x+1);
 17     chosen.pop_back();//回溯到原始
 18 }
 19 int main(){
 20     cin >> n;
 21     calc(1);
 22     return 0;
 23 }

追求吾之所爱