题目描述

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

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

样例

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

深搜过程：两个未被执行完需先搁置的状态：dfs执行过程的调用，for中i的遍历

1. dfs执行过程的调用（通过递归出口向上返回，然后向下执行语句（回溯：删掉该状态下该值已被用过的状态））
   2.通过for循环现 判断该状态下是否有比i大，且未被用过的i
   {
   分为两种状态：

   1. i已为最大值 （退出for循环，返回上一层dfs调用）
   2. 有比此时i大的值，且未被用过，则该层更新为新的i，继续向下执行;

   }
   for循环作用：遍历每一种状态，实现每个节点的值都不会被遗漏
   注：先清空该i值已被用过的状态，后通过for循环遍历该层（u）是否有满足条件的值，是否可以更新该状态

#include<bits/stdc++.h>
using namespace std;
int n;
const int N=10;

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

void dfs(int u)
{
    if(u==n)
    {
        for(int i=0;i<n;i++)
        {
            cout<<st[i]<<" ";
        }
        cout<<endl;
    }
    else
    {
        for(int i=1;i<=n;i++)
        {
            if(!path[i])//是否有满足条件的值
            {
                st[u]=i;//是否可以更新该状态
                path[i]=true;
                dfs(u+1);
                path[i]=false;//先清空该i值已被用过的状态，后通过for循环遍历该层（u）是否有满足条件的值，是否可以更新该状态
            } 
        } 
    }
}
int main()
{
    cin>>n;
    dfs(0);
    return 0;
}