AcWing 94. 递归实现排列型枚举 (带详细注释和思路)
原题链接
简单
作者:
SaIieri
,
2022-02-28 21:11:28
,
所有人可见
,
阅读 210
/* 这道题我们需要一个变量统计位置:u
需要判断一个数字是否用过:usedd[]
需要一个数组来存数据:a[]
需要一个循环轮流放入1~n */
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <iostream>
using namespace std;
const int N=10;
int a[N];
bool usedd[N]={0};
int n;
void dfs(int u)
{
//输出的部分
if(u>n)
{
for(int i=1;i<u;i++)
{
printf("%d ",a[i]);
}
puts("");
return;
}
/*以下为进行的dfs操作*/
for(int x=1;x<=n;x++)//在树的每一层依次轮换着放入1~n 这n个数字 可以自己画一个树结合着来看
{
if(usedd[x]==0)//判断1~n这些数中轮到的数字有没有用过
{
a[u]=x;//将轮到的数字放入对应的第u个位置
usedd[x]=1;//代表这个x这个数字用过了
dfs(u+1);
a[u]=0;//恢复原样 0表示空的位置,没有数字
usedd[x]=0;//数字x从位置上拿下 恢复自由的状态
}
}
}
int main()
{
cin >> n;
dfs(1);
return 0;
}