AcWing 92. 递归实现指数型枚举
原题链接
简单
作者:
A霜序二三.
,
2024-04-24 22:13:09
,
所有人可见
,
阅读 1
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 20;
int st[N];//记录每个数的状态,0表示还没考虑,1表示选这个数,2表示不选这个数
int n;
void dfs(int x)
{
//如果已经搜到n那么超过的将不再搜索
if(x > n)
{
for(int i = 1; i <= n; i++)//遍历
{
if(st[i] == 1)cout<<i<<" ";//如果选了,就打印它的下标
}
cout<<'\n';//注意换行
return;
}
//选
st[x] = 1;
dfs(x+1);//进行下一行搜索
st[x] = 0;//恢复现场
//不选
st[x] = 2;
dfs(x+1);
st[x] = 0;//恢复现场
//所谓恢复现场是因为你如果先选了,那么要想判断没有选的情况
//必须先回溯到原来的位置再判断没有选的情况
}
int main()
{
cin>>n;
dfs(1);//从1开始选,进行深度搜索
return 0;
}
我感觉这个更好理解