从 1∼n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。
输入格式
输入一个整数 n 。
输出格式
每行输出一种方案。
同一行内的数必须升序排列，相邻两个数用恰好 1 个空格隔开。
对于没有选任何数的方案，输出空行。
本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。
数据范围
1 ≤ n ≤ 15
输入样例：
3
输出样例：
3 2 2 3 1 1 3 1 2 1 2 3
思路
这里实际上就是自己手写一个判断，对三个位置进行判断，每个位置分别有两种情况，选或者不选，分别用1、2表示；也是用到了dfs深搜，利用递归，从每个数都是2（不选）开始，进行递归，归的时候已经恢复现场了，直接采用第二种方案 选 ，然后递归进去输出 / 定义一个二维数组记录结果，不过这种情况有点麻烦。
Code
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int N = 16; int n; int st[N];//状态，记录每个位置当前的状态，0，未考虑，1选，2不选 vector<vector<int>> ways; //二维数组 void dfs(int u) //u表示当前我们正在做第几位 { if(u > n) //边界 { vector<int> way; for(int i = 1; i <= n;i ++) //记录方案 if(st[i] == 1) //当前位置为1，表示我们选了，输出 way.push_back(i); ways.push_back(way); // 把way方案存到ways里面去 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);//st数组是全局的，不用传进去 for (int i = 0; i < ways.size(); i ++) { for (int j = 0; j < ways[i].size(); j ++ ) printf("%d ",ways[i][j]); puts("");//输出一个空字符串+换行 } return 0; }
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 16; int n; int st[N]; // 状态，记录每个位置当前的状态：0表示还没考虑，1表示选它，2表示不选它 void dfs(int u) { if (u > n) { for (int i = 1; i <= n; i ++ ) if (st[i] == 1) printf("%d ", i); printf("\n"); 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); return 0; }
