思路：枚举每个位置放置哪个数 本人最喜欢的枚举方式

#include<iostream>
#include<vector>
using namespace std;
vector<int> ans;
int n;
void dfs(int u,int state)
{
    if(u==n+1)
    {
        for(int i=0;i<ans.size();++i)cout<<ans[i]<<" ";
        cout<<endl;
        return;
    }
    //枚举当前位置放哪个数
    for(int i=0;i<n;++i)
    {
        if((state>>i) &1) continue;
        ans.push_back(i+1);
        dfs(u+1,state|(1<<i));
        ans.pop_back();
    }
}
int main()
{
    cin>>n;
    dfs(1,0);
    return 0;
}

思路二：这个思路在这道题是不能ac的，但是这个思想很重要。
枚举每个位置放置哪个数，如果枚举到了n+1说明已经得到答案，输出并返回即可。
为什么不对呢？
只讨论第一个数的情况下，在递归搜索树上它是放在1-n 每个位置上共n个分支。
此时输出就分成了n块 分别是 1在第一个位置 1在第二个位置 1在第三个位置 ----
实际上比如1在2 3 – 位置上时，由于是字典序，那么总能找到1在后面位置的时候的排列的前面的数的字典序是比
当前数的小的(n>=3)。

#include<iostream>
#include<vector>
using namespace std;
const int N = 10;
int num[N];
int n;
void dfs(int u)
{
    if(u==n+1)//1-u 都已经枚举完 得出答案
    {
        for(int i=1;i<=n;++i)cout<<num[i]<<" ";
        cout<<endl;
        return;
    }
    //枚举当前这个数放在哪个位置
    for(int i=1;i<=n;++i)
    {
        if(!num[i]){
            //放进去
            num[i]=u;
            dfs(u+1);
            num[i]=0;
        }
    }
}
int main()
{
    cin>>n;
    dfs(1);
    return 0;
}

思路三：STL 考试最便捷的做法 但是普适性太低

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 10;
int num[N];
int n;
int main()
{
    cin>>n;
    for(int i=0;i<n;++i)num[i]=i+1;
    do{
        for(int i=0;i<n;++i)cout<<num[i]<<" ";
        cout<<endl;
    }while(next_permutation(num,num+n));
    return 0;
}