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

开一个now数组存储当下哪些数用过了。

因为要求字典序，所以直接从$1$到$n$遍历选下一个。

C++ 代码

#include<iostream>
#define fs(i,x,y,z) for(int i=x;i<=y;i+=z)
using namespace std;
int n,a[101],usd[101];
void dfs(int now){
    if(now>n){
        fs(i,1,n,1) cout<<a[i]<<' ';
        cout<<endl;
        return;
    }
    fs(i,1,n,1){
        if(!usd[i]){
            usd[i]=1;
            a[now]=i;
            dfs(now+1);
            usd[i]=0;
        }
    }
}
int main(){
    cin>>n;
    if(n==1){
        cout<<1;
        return 0;
    }
    dfs(1);
    return 0;
}