题目大意

输入$n$，把$1$到$n$这$n$个整数打乱顺序，输出所有方案，要求行与行间以字典序由小到大输出

解题思路

此题与指数型枚举不同的点在于，每个数都一定会被选上，只是出现的位置不一定。第一次做此题的初学者可能会陷进实现指数型枚举的思路中，每层dfs考虑当前数应该放在哪一个位置，硬要这么做也可以，但写完以后会发现输出顺序并不天然地满足要求行与行间以字典序由小到大输出。偏执的朋友可能会存下所有方案再实现一个排序来通过此题。事实上本题换一种方法设计dfs即可，即每层dfs考虑当前位置应该放哪一个数。

具体代码

#include<iostream>
using namespace std;
const int N=15;
bool st[N];
int path[N];
int n;
void dfs(int u) //当前正在考虑第u个位置
{
    if(u==n+1) //所有位置都已经考虑完了选哪个数
    {
        for(int i=1;i<=n;i++)
            cout<<path[i]<<' ';
        puts("");
    }

    for(int i=1;i<=n;i++) //考虑当前位置选哪个数
    {
        if(!st[i]) //选择的数之前不能被选过
        {
            st[i]=true;
            path[u]=i;
            dfs(u+1);
            st[i]=false; //回溯恢复现场
            path[u]=0; //这条命令没有用，只是为了对称美观
        }
    }

}
int main()
{
    cin>>n;
    dfs(1);
    return 0;
}