dfs

(暴力枚举) $O(n!*n)$

/*
递归：
工具：st[]标记访没访问过，key[]记录最终的数组
大体思路：

            /   \   \
           0    0   0     //每一层代表最终数组的每一个位置 index
          / \  / \  / \
         0  0 0   0 0  0
*/


#include<iostream>
#define N 10
using namespace std;

int key[N];

int st[N];
    int n;
void dfs(int index){
    if(index==n){
    for(int i=0;i<n;++i){
         cout<<key[i]<<' ';
    }
    cout<<endl;
        return;
    }

    for(int i=1;i<=n;++i){
        if(!st[i]){
            st[i]=true;
            key[index]=i;
            dfs(index+1);
            st[i]=false;
        }

    }


}


int main(){

    cin>>n;
    dfs(0);


    return 0;
}