题目描述 //不清楚过程就手动模拟

给定一个整数n，将数字1~n排成一排，将会有很多种排列方法。

现在，请你按照字典序将所有的排列方法输出。

输入格式
共一行，包含一个整数n。

输出格式
按字典序输出所有排列方案，每个方案占一行。

数据范围
1≤n≤7
输入样例：
3
输出样例：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

C++ 代码

#include<iostream>
using namespace std;
const int N=10;
int arr[N];
int book[N];
int n;
void dfs(int x)
{
    if(x>n)      //放完了3个元素/已经形成一个全排列   //不能取等号
    {
        for(int i=1;i<=n;i++)
        {
            cout<<arr[i]<<" ";
        }
        cout<<endl;   //这里没有return;
    }                 //所以函数会继续去执行下面的for循环。但是3个数字都被使用了。所以一次if语句也进不去。
    for(int i=1;i<=n;i++)                                 // 然后函数执行结束返回到上一次调用它的地方。

    {                    //因为上次已经循环到i=3的位置，所以接下来会取消对数字3的标记。让它变为未占领状态。
        if(!book[i])     //接着i增加到4不满足for循环。 然后函数执行结束返回到上一次调用它的地方。
        {                                                  
          arr[x]=i; //放当前值到数组中/放当前值进入当前盒子
          book[i]=1;//标记这个数字已经使用
          dfs(x+1); //放入下一个值到数组中/放元素进入下一个盒子
          book[i]=0;//记得回溯
        }
    }                  //因为上次已经循环到i=2的位置。所以接下来会取消对2的占领状态。此时x=2不会发生变化
}                      //然后i++，i的值变为3。因为上个函数中取消了对3的标记。所以3可用。所以2号盒子里放入3
int main()             //接下来会将数字3标记为占有状态。再调用dfs(x+1)。(x+1=3)
{                    
    cin>>n;            //接下来发现数字2可用。于是得到1 3 2的全排列。然后打印返回之后取消对数字2的标记
    dfs(1);            //然后i++,i的值变为3。因为数字3已经被标记占用，所以进不了for循环。
    return 0;          //接着i增加到4不满足for循环。 然后函数执行结束返回到上一次调用它的地方。
}
                       //这个函数的for循环上一次已经执行到了i=3的地方。所以接下来会取消对数字3的占领状态
                       // 接着i增加到4不满足for循环。 然后函数执行结束返回到上一次调用它的地方。

                       //也就是回到最初的那个循环。然后取消对数字1的占领状态。
                       //接着i++,i的值变为2.此时这个循环中x=1不会发生变化。
                       //将2放入1号盒子。接下来会将数字2标记为占有状态

                      // 以此规律继续。直到最初的函数那个for循环结束便会得到所有的结果

                       //接着会在2号盒子中发现数字1满足。所以得到2 1