AcWing 92. 递归实现指数型枚举
原题链接
简单
作者:
hi_1128
,
2024-04-11 16:03:48
,
所有人可见
,
阅读 1
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=16;//注意定义成常变量 vector中才能用N
int sta[N];//表状态,0未考虑 1选了 2未选
int n;//注意n是要输入的,全局变量
vector<vector<int> >ways;//别放函数里,不然被释放了main函数用不了
void dfs(int u)
{
//全都遍历完
if(u>n)
{
//存入方案
vector<int>way;//注意位置 每次遍历完成后才创建数组,结束了也就释放了
for(int i=1;i<=n;i++)
if(sta[i]==1) //忘判断条件了,可以写上注释自己在干嘛
// way.pushback(sta[i]) ;
way.push_back(i);
ways.push_back(way);
return;//别忘了!!!
}
//不恢复原状态好像也能过
sta[u]=1;//选了他,进入下一层 恢复原样
dfs(u+1);
sta[u]=0;
sta[u]=2;//第二个分支 没选他 进下一层 恢复原样
dfs(u+1);
sta[u]=0;
}
int main()
{
cin>>n;
dfs(1);
//输出
// for(int i=1;i<=ways.size();i++) 错误 因为ways是直接pushback的 下标0对应第一个位置
//
// for(int j=1;j<ways[i].size();j++)//注意是ways[i]而不是way
// {
// printf("%d",ways[i][j]);
// puts("");
// }
for(int i=0;i<ways.size();i++)
{
for(int j=0;j<ways[i].size();j++)//注意是ways[i]而不是way
printf("%d ",ways[i][j]);
puts("");
}
system("pause");
return 0;