题目描述

https://www.acwing.com/problem/content/844/

y总名言：DFS - 最重要的就是顺序问题，本题解用两种搜索顺序。

算法1

顺序：以 path[N]的每个格子为顺序，从第 0 个格子，枚举到最后一个格子

C++ 代码

#include <iostream>

using namespace std;

const int N = 10;

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

void dfs(int u)
{
    if (u == n) // 如果已经到最后一个格子了，直接输出
    {
        for (int i = 0; i < n; i ++ )
            cout << path[i] << ' ';
        cout << endl;
        return;
    }

    // path[u] 这个格子能够填入哪个数？
    // 枚举，然后填入 - 递归到下一个格子
    for (int i = 1; i <= n; i ++ )
    {
        if (!st[i])
        {
            st[i] = true;
            path[u] = i; // 填入数
            dfs(u + 1); // 递归到下一个格子
            st[i] = false;
        }
    }
}

int main()
{
    cin >> n;

    dfs(0); // 顺序 - 从 path[N] 的第 0 号格子开始枚举，直到最后一个格子

    return 0;
}

算法2

顺序：以每个数字为顺序，看看能填入到哪个格子

从 1 开始枚举，填入某个格子；递归到最后一个数 n

（这种顺序没有保证按字典序输出，所以无法 AC，可以尝试尝试）

C++ 代码

#include <iostream>

using namespace std;

const int N = 10;
int n;
int path[N];
bool st[N];

void dfs(int i)
{
    if (i == n + 1) // 如果 1 - n 已经填完了，就输出
    {
        for (int i = 0; i < n; i ++ )
            cout << path[i] << ' ';
        cout << endl;
        return;
    }

    // 从 path[0] 开始枚举，看看数字 i 能填到哪个格子
    for (int j = 0; j < n; j ++ )
    {
        if (!st[j])
        {
            st[j] = true;
            path[j] = i; // 如果这个格子没有被填过，就把 i 填进去
            dfs(i + 1);
            st[j] = false;
        }
    }
}

int main()
{
    cin >> n;

    // 从数字 1 开始，填入某个格子，一直递归到 n
    dfs(1);

    return 0;
}

输出：

1 2 3 
1 3 2 // 1 能够填 path[0]
2 1 3 
3 1 2 // 1 -> path[1]
2 3 1 
3 2 1 // 1 -> path[2]