AcWing 92. 递归实现指数型枚举
原题链接
简单
作者:
AC_modesty
,
2024-02-13 17:10:23
,
所有人可见
,
阅读 1
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=16;//开数组
int state[N];//状态数组,0表示还未考虑,1表示选了,2表示不选
int n;//选数范围
void dfs(int u)//广度优先遍历
{
if(u>n)//先考虑边界
{
for(int i=1;i<=n;i++)//遍历所有数字
{
if(state[i]==1)
cout<<i<<" ";//只要状态数组是1,即状态为已选,则打印出来
}
cout<<endl;
return;
}
state[u]=2;//第一分支,不选的情况
dfs(u+1);//考虑下一个位置
state[u]=0;//恢复现场
state[u]=1;//第二分支,选的情况
dfs(u+1);//考虑下一个位置
state[u]=0;//恢复现场
}
int main()
{
cin>>n;
dfs(1);
return 0;
}