题目描述
从 1~n 这 n 个整数中随机选取任意多个,输出所有可能的选择方案。
输入格式
输入一个整数n。
输出格式
每行输出一种方案。
同一行内的数必须升序排列,相邻两个数用恰好1个空格隔开。
对于没有选任何数的方案,输出空行。
本题有自定义校验器(SPJ),各行(不同方案)之间的顺序任意。
数据范围
1≤n≤15
输入样例:
3
输出样例:
3
2
2 3
1
1 3
1 2
1 2 3
### 算法1
#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;
}
作者:yxc
假设 n = 3,即我们有一个包含3个元素的集合,比如集合 {1, 2, 3}。
递归过程
初始调用:dfs(1)
此时,u = 1,即我们考虑第一个元素(1)。
1.第一个分支(不选1):
st[1] = 2(不选1)
调用 dfs(2)
此时,u = 2,考虑第二个元素(2)。
2. 第一个分支(不选2):
st[2] = 2(不选2)
调用 dfs(3)
此时,u = 3,考虑第三个元素(3)。
3.第一个分支(不选3):
st[3] = 2(不选3)
4.调用 dfs(4),但 u > n,所以打印当前子集(空集),并返回。
3.第二个分支(选3):
st[3] = 1(选3)
4.调用 dfs(4),打印当前子集({3}),并返回。
恢复 st[2] = 0
2.第二个分支(选2):
st[2] = 1(选2)
调用 dfs(3)
类似地,这会探索 {2, 3} 和 {2} 这两个子集。
恢复 st[2] = 0
恢复 st[1] = 0
1.第二个分支(选1):
st[1] = 1(选1)
调用 dfs(2)
类似地,这会探索 {1}、{1, 2}、{1, 3} 和 {1, 2, 3} 这四个子集。
恢复 st[1] = 0