从 1∼n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。
输入格式
输入一个整数 n。
输出格式
每行输出一种方案。
同一行内的数必须升序排列，相邻两个数用恰好 11 个空格隔开。
对于没有选任何数的方案，输出空行。
本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。
数据范围
1≤n≤15
输入样例：
3
输出样例：
3 2 2 3 1 1 3 1 2 1 2 3
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int N = 16; int n; int st[N]; //记录每个位置当前状态 0还没考虑 1选他 2不选他 int ways[1 << 15][16], cnt; void dfs(int u) { if (u > n) { for (int i = 1; i <= n; i++) { if (st[i] == 1) { ways[cnt][i] = i; } } cnt++; return; } st[u] = 2; dfs(u + 1); //第一个分支 不选 st[u] = 0; //恢复现场 st[u] = 1; dfs(u + 1); //第二个分支 选 st[u] = 0; } int main() { cin >> n; dfs(1); for (int i = 0; i < cnt; i++) { for (int j = 1; j <= n; j++) { if(ways[i][j]!=0) { printf("%d ", ways[i][j]); } } puts(""); } return 0; }
