题目
从 1~n 这 n 个整数中随机选取任意多个,输出所有可能的选择方案。
输入格式
输入一个整数n。
输出格式
每行输出一种方案。
同一行内的数必须升序排列,相邻两个数用恰好1个空格隔开。
对于没有选任何数的方案,输出空行。
本题有自定义校验器(SPJ),各行(不同方案)之间的顺序任意。
输入样例
3
输出样例
3
2
2 3
1
1 3
1 2
1 2 3
思路
递归
,二进制状态压缩
,顺序枚举
递推版
- 前后关系:f[n] = f[n - 1] + 操作
- 子问题状态:u
- 递归结果:无返回值,全局变量vector
> num - 递归出口:n == 0
并列版
- 前后关系:从小到大枚举每位数是否被选
- 子问题状态:u和state(被选情况)
- 递归结果:无返回值,形参state
- 递归出口:无剪枝,结束u == n
dfs中非引用型形参,其状态值在当前函数不变。不需要手动回溯。
dfs(u + 1, state | (1 << u)); //选
dfs(u + 1, state); //不选
代码实现
递推版
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> num;
void dfs(int n)
{
if (n == 0) return;
dfs(n - 1);
vector<vector<int>> tmp; //局部变量
for (auto u : num) //不插入破坏原num
{
auto t = u;
t.push_back(n);
tmp.push_back(t);
}
for (auto u : tmp) num.push_back(u);
num.push_back({n});
}
int main()
{
int n;
cin >> n;
dfs(n);
for (auto u : num)
{
for (auto it : u) cout << it << " ";
cout << endl;
}
}
并列版
#include <iostream>
using namespace std;
int n;
void dfs(int u, int state)
{
if (u == n)
{
for (int i = 0; i < n; i++)
{
if (state >> i & 1) cout << i + 1 << " "; //state从0开始,数值需要加1
}
cout << endl;
return;
}
//两次递归状态相同
dfs(u + 1, state | (1 << u)); //选
dfs(u + 1, state); //不选
}
int main()
{
cin >> n;
dfs(0, 0); //从0开始顺序枚举,保证升序
}