【AcWing算法基础】第三讲-搜索与图论-DFS AcWing 842. 排列数字

摘要：
DFS入门题。

题目

给定一个整数 $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++
Java

#include <bits/stdc++.h>

using namespace std;

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

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

int main()
{
    cin >> n;
    dfs(0);
}

1
2

理解

本题核心思想是使用递归全量枚举暴搜。

按照深度优先进行下一位数字的搜索操作。每搜索到一个节点，使用path数组记录节点值。当路径中记录的数字数量到达预计值的时候，输出路径并递归返回。

为了每个节点可以使用新的数字而不至于重复，将当前路径已经使用过的数字使用额外数组记下，在下一层调用的时候跳过已使用的数字。

需要注意的是，在递归回来的时候，需要将已被标记的当前入口节点使用状态重置。因为标记的目的是为了下一层跳过，那么从下一层递归回来当然需要还原。

另外，之所以回溯的时候，path不需要恢复现场，是因为后续的写入会直接将对应位置的值覆盖掉。

原题链接： AcWing 842. 排列数字