AcWing 94. 递归实现排列型枚举
原题链接
简单
作者:
骄骄是骄傲的骄骄
,
2022-02-15 21:13:49
,
所有人可见
,
阅读 144
/*
输出 1-n 的所有排列方式
相当于在一个数组中填入不重复数字
那么数组中的某个元素,是未选择的数字
而题目要求字典序输出
那么一定是 未选择的数字中最小的数字
边界条件:
最后一个数已经选取
*/
#include <iostream>
using namespace std;
int n;
int res[10], used[10];
// 当前位置
void dfs(int u){
// 边界情况
if(u>n){
for(int i=1; i<=n; i++)
printf("%d ", res[i]);
puts("");
return ;
}
// 最小的数字,那么从首个数字检查使用情况
for(int i=1; i<=n; i++){
if(used[i]) continue;
used[i]=1;
res[u]=i;
dfs(u+1);
used[i]=0;
res[u]=0; // 恢复现场
}
}
int main(){
cin>>n;
dfs(1);
return 0;
}