AcWing 842.排列数字

思路分析：听了Y总的思路之后，我一开始复现写的核心代码是这样的：

 void dfs(int u)
{
    if(u > n)
    {
        for(int i = 0; i < n; i++) printf("%d ", path[i]);
        printf("\n");
        return;
    }

    for(int i = 0; i < n; i++)
    {
        if(!st[i])
        {
            path[i] = u;
            st[i] = true;
            dfs(u + 1);
            path[i] = 0;
            st[i] = false;    
        }
    }
    return;

}

问题就出在"path[i] = u;"这一句上。由于我是将u赋值给path[i],等于是说，我是每次选择一个数字，将每个数字
分配到每个位置上，而不是进入一个位置，将数字放置进去，这样的思路虽然也能够输出全排列，但是就与题目中要
求的顺序不符了。而且，这样的话，我的dfs也得由dfs(1)进入，而不是从dfs(0)进入了。因为前者的dfs(*)里的*是
数字的值，后者的dfs(*)里的*是放置数字的第一个位置。完整代码和错误输出结果如下:

完整代码:

#include <iostream>
using namespace std;
const int N = 10;
int path[N];
bool st[N] = {0};
int n;
void dfs(int u)
{
    if(u > n)
    {
        for(int i = 0; i < n; i++) printf("%d ", path[i]);
        printf("\n");
        return;
    }

    for(int i = 0; i < n; i++)
    {
        if(!st[i])
        {
            path[i] = u;
            st[i] = true;
            dfs(u + 1);
            path[i] = 0;
            st[i] = false;    
        }
    }
    return;

}

int main()
{
    scanf("%d", &n);
    dfs(1);
    return 0;
}

错误的输出:
1 2 3
1 3 2
2 1 3
3 1 2
2 3 1
3 2 1

正确代码:
#include <iostream>
using namespace std;
const int N = 10;
int path[N];
bool st[N] = {0};
int n;
void dfs(int u)
{
    if(u == n)
    {
        for(int i = 0; i < n; i++) printf("%d ", path[i]);
        printf("\n");
        return;
    }

    for(int i = 1; i <= n; i++)
    {
        if(!st[i])
        {
            path[u] = i;
            st[i] = true;
            dfs(u + 1);
            path[u] = 0;
            st[i] = false;
        }
    }

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

标准答案:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1