Acwing 823.排列

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

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

输入格式

共一行，包含一个整数 n。

输出格式

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

数据范围

1≤n≤9

输入样例：

3

输出样例：

1. 1 2 3
2. 1 3 2
3. 2 1 3
4. 2 3 1
5. 3 1 2
6. 3 2 1

问题分析：这是一道DFS的题目 借用大佬的图

对此展开分析：

vis[i]用于标记数组，p[i](position）用于记录第i位（从左往右）上的数字是什么

那么对于n = 3，我们从第一个位置(u)开始枚举,dfs(1)

遍历 1—3,选取一个数,如果这个数没被访问过，那么把这个位置填入第1（u）个位置，同时标记这个数字已访问，继续搜第二个位置dfs(2)...

当dfs(2）搜完了以后，代表第一个位置是1（假设是1）的所有情况已经枚举完了，此时需要标记上一步即第一个位置的数字未访问，为的是后来能够再次用到这个数字；

基线条件：当u=n+1,说明1—n位置都有数字填进去了，那么把它输出就可以了；

注意，因为要按字典序输出升序，所以每次在遍历的时候，从1到9这样的顺序考虑就好了

#include <iostream>
using namespace std;
int n;
int vis[10];
int p[10];
void dfs(int u)
{
    if (u==n+1)
    {
        for (int i =1;i<=n;i++) cout<<p[i]<<" ";
        cout<<endl;
    }
    else
    {
        for (int i =1;i<=n;i++)
        {
            if (!vis[i])
            {
                p[u] = i;
                vis[i] = 1;
                dfs(u+1);
                vis[i] = 0;
            }
        }
    }
}
int main()
{
    cin >>n;
    dfs(1);
    return 0;
}

还是感觉深搜有点不太好理解qwq，多做点题目找找感觉吧- -