这是一道非常经典的dfs问题，是每个初学dfs同学首先要面对的问题。
我们把这个问题形象化，以便更好的理解。
说张三有编号分别为1， 2， 3的美女出浴图，现在为了不要被李四发现，需要把这三张图片放到密码箱里。而且藏得时候呢，为了稳妥起见，需要将三张图片分别放在三个箱子内，每一个箱子都要放一张，毕竟前人警告我们，不要把鸡蛋放在一个篮子里。

现在张三要考虑的就是怎么来放这些图片（即为图片的顺序），因为张三是一个科学家，希望可以通过实践来知道有多少种放照片的顺序。

现在张三走到第一个箱子，不过他有些困惑，该放那一张好呢，是1图、2图、还是3图呢。不要着急，我们每一种放图片的方式都会尝试，我们先来按顺序放吧。
于是，1图放进1号箱子内。

现在张三将1图放进了1号箱内，然后就走到了2号箱旁边，因为手里已经没有了1图，只好放入2图了
2号箱放入照片后，张三就来到了2号箱旁边，由于手里只有一张照片了，就把它放入了3号箱内。

3号箱放好后，张三来到四号箱，但是手里已经没有照片了，回头一看，原来早就排好序了。顺序即为1 -> 2 -> 3

但是这得到的只是一种排序，并不是全部的排序，所以张三决定往回走。
张三往回走走到3号箱，取出了3图，在这里他想向空的3号箱放入照片，但是手里只有3图，张三只好再往回走。张三往回走走到了2号箱，将2号箱里的2图取出，现在他的手里有两张照片了，于是按照新的方式，张三将3图放入2号箱内，再走到3号箱放入2图。

于是我们又得到了一种新的排序方法 ：1 -> 3 -> 2

我们这种方式，接着进行模拟，可以得到余下的排序方法：2 -> 1 -> 3; 2 -> 3 -> 1; 3 -> 1 -> 2; 3 -> 2 -> 1;

下面要做的就是将模拟的过程代码化。

#include <iostream>

using namespace std;

const int N = 10;

int n;
int path[N];
bool st[N];

void dfs(int u){
    if (u == n + 1){//当走到n+1号箱的时候，说明已经走完了
        for (int i = 1; i <= n; i ++ ) printf("%d ", path[i]);
        puts("");
        return;//这个return非常重要，它就是一直困惑着我的原因
        //return的作用是返回上一步
    }

    for (int i = 1; i <= n; i ++ )
        if (!st[i]){//判断i图是否还在手里
            path[u] = i; //将i图放入u号箱子
            st[i] = true;//标记：i图不在手中了，而是已经在箱子内了
            dfs(u + 1);//张三走到下一个箱子
            st[i] = false;//将放入u号箱的图片收回。

        }
}
int main(){
    scanf("%d", &n);

    dfs(1);//从1号箱开始模拟

    return 0;
}

在加上一个，STL刚开始学，还是要多练练滴

#include <iostream>
#include <vector>

using namespace std;

const int N = 20;

int n;
vector<int> path;//表示路径
bool st[N];
void dfs(int u){
    if (u == n){
        for (auto x : path) cout << x << ' ';//auto遍历，真方便
        cout << endl;//换行
        return;
    }

    for (int i = 0; i < n; i ++ )
        if (!st[i]){
            path.push_back(i + 1);//在尾部添加元素，添加的i要加1，是因为i从0开始
            st[i] = true;//这个数用过了
            dfs(u + 1);//开始下一层
            path.pop_back();//将刚才的加进去的元素给吐出来，俗称还原
            st[i] = false;//也是还原
        }
}
int main(){
    cin >> n;

    dfs(0);

    return 0;
}