AcWing 94. 递归实现排列型枚举
原题链接
简单
作者:
Galaxy_06
,
2024-03-25 22:05:06
,
所有人可见
,
阅读 1
排列型枚举要注意套一个o(n)的扫描最小未用值
复杂度9!*9*9
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 20;
int st[N];
bool used[N];
int n;
int get_unused_min(){
for(int i = 1; i <= n; i++) if(used[i] == false) return i;
}
void dfs(int h){
if(h == n){
for(int i = 1; i <= n; i++) printf("%d ", st[i]);
puts("");
}
for(int i = get_unused_min(); i <= n; i++){
if(used[i] == true) continue;
st[h + 1] = i;
used[i] = true;
dfs(h + 1);
st[h + 1] = 0;
used[i] = false;
}
}
int main(){
cin >> n;
dfs(0);
return 0;
}