题目大意
输入$n$,输出从$1$到$n$中选任意多个数的所有方案,要求同一行内是升序
解题思路
每个数都有选与不选两种情况,选与不选产生两种分支,因此dfs需要关心的状态有:当前正在考虑第几个数,已经考虑完了的数是选了还是没选
具体代码
#include<iostream>
using namespace std;
const int N=20;
int n;
bool st[N];
void dfs(int u) //当前正考虑第u个数选不选
{
if(u==n+1) //当前分支已经考虑完了所有数
{
for(int i=1;i<=n;i++)
{
if(st[i]) cout<<i<<' ';
}
puts("");
return;
}
//选当前数的分支
st[u]=true;
dfs(u+1);
st[u]=false; //回溯恢复现场
//不选当前数的分支
dfs(u+1);
}
int main()
{
cin>>n;
dfs(1);
return 0;
}