这等价于每个整数可以选或者不选,总共2^n
使用递归求解,在每次递归中分别尝试每个位置的数选或者不选两条分支, (将选的位置数字进行标记,直至分支结束,逐个打印)
将未确定的整数数量减少1,从而转化为规模更小的子问题。
// 选择合适的顺序,不重不漏的将每个数打印出来
// 从1-n依次考虑每个数选或者不选,形成递归树
// 一行最多输出n个数,考虑每个位置是否使用过、选、不选
// 下标从1开始
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 20;
int count=0;
int n, path[N];
int st[N]; //状态,记录每个位置当前状态; 0表示还没考虑, 1表示选, 2表示不选
// 下标1-n 代表 数字本身, st[i] 代表这个数字要不要被选
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()
{
scanf("%d", &n);
dfs(1);
return 0;
}