题解
#include <iostream>
using namespace std;
int used[10];//简单用个数组记录是否使用
int state[10];//记录该位置是哪个数
int n;
void dfs(int u){
if(u>n){
for(int i=1;i<=n;i++){
cout << state[i] << " ";
}
cout << endl;
return;
}
for (int i=1;i<=n;i++){
if (used[i]==0){
state[u]=i;
used[i]=1;
dfs(u+1);
//恢复现场
state[u]=0;
used[i]=0;
}
}
}
int main(){
cin >> n;
dfs(1);
return 0;
}
时间复杂度
递归调用次数为 n!,每次递归都要遍历 n
O(n*n!)
?
一个dfs 里面要 for,因为是有可能用回前面的数的