递归实现指数型枚举

方法一：二进制状态枚举

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N = 20;
 4 int n;
 5 int main() {
 6     cin >> n;
 7     for (int i = 0; i < (1 << n); i++) { //枚举所有状态
 8         for (int j = 0; j < n; j++) { //枚举每一位
 9             if (i >> j & 1) { //如果该位是1，表示选择
10                 cout << j + 1 << " ";
11             }
12         }
13         cout << endl;
14     }
15     return 0;
16 }

方法二：dfs

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int n;
 4 int st[20]; //标记每一个数有没有被选，0表示还没考虑，1表示选，2表示不选
 5 void dfs(int u) { //判断u这个数要不要选
 6     if (u == n + 1) { //如果n个数都已经判断完了
 7         for (int i = 1; i <= n; i++) { //遍历n个数
 8             if (st[i] == 1) { //如果该点选择了
 9                 cout << i << " "; //输出该点
10             }
11         }
12         cout  << endl;
13         return;
14     }
15     //不选u这个数
16     st[u] = 2;
17     dfs(u + 1);
18     st[u] = 0; //回溯恢复现场
19     //选u这个数
20     st[u] = 1;
21     dfs(u + 1);
22     st[u] = 0; //回溯恢复现场
23 }
24 int main() {
25     cin >> n;
26     dfs(1); //从数1开始搜索，判断其要不要选择
27     return 0;
28 }

方法三：递归，其实递归和dfs本质上是相同的，不过也是另外一种思路

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 vector<int> chosen;
 4 int n;
 5 void calc(int x) {
 6     if (x == n + 1) {
 7         for (int i = 0; i < chosen.size(); i++) {
 8             cout << chosen[i] << " ";
 9         }
10         cout << endl;
11         return;
12     }
13     //不选x这个数
14     calc(x + 1);
15     //选x这个数
16     chosen.push_back(x);
17     calc(x + 1);
18     chosen.pop_back(); //回溯还原现场
19 }
20 int main() {
21     cin >> n;
22     calc(1);
23     return 0;
24 }