递归实现指数型枚举
从 1∼n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。
输入格式
输入一个整数 n。
输出格式
每行输出一种方案。
同一行内的数必须升序排列，相邻两个数用恰好 1 个空格隔开。
对于没有选任何数的方案，输出空行。
本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。
数据范围
1≤n≤15
输入样例：
3
输出样例：
3
2
2 3
1
1 3
1 2
1 2 3
思路
dfs递归搜索树 (注意理解递归流程)
Code
点击查看代码
#include<iostream>
using namespace std;
int n;
int st[20]; //记录是否选择
void dfs(int x){ //x代表选到x
if(x > n){ //如果x > n说明已经形成一个方案
for(int i = 1; i <= n; i ++ ){
if(st[i])cout << i << " "; //如果方案选择了i则输出
}
puts("");
return ; //结束递归
}
st[x] = 0; //选x
dfs(x + 1); //选下一位
st[x] = 1; //不选x
dfs(x + 1);
}
int main(){
cin >> n;
dfs(1); //从第1位开始选 //枚举每一位是否选择
return 0; //每一位选或者不选，总共2^n种方案
}