DFS 入门：从汉诺塔到 n 的全排列

上学期在 JavaEE 学习中第一次接触 DFS 思想，是从汉诺塔问题开始的。汉诺塔很适合作为递归入门：把一个大问题拆成“先移动上面的盘子、再移动当前盘子、最后移动剩下的盘子”。

这学期补算法题时，又遇见了一个很典型的问题：n 的全排列。

题目描述

输入一个数字 n。

输出从 1 到 n 这 n 个数字组成的所有长度为 n 的排列。

例如输入 3，可以输出：

DFS 思想

这道题仍然是 DFS 的思想。

写递归时，可以先考虑“当前这一步做什么”，或者假设当前只有一步要完成。这一点很像分治：先把当前层的问题想清楚，再把剩下的问题交给下一层递归。

在全排列里，当前这一步就是：

给当前位置 temp 选择一个还没有使用过的数字。

比如第三个数字也可能成为第二个位置上的数字，所以每一层都要从 1 到 n 重新枚举。但为了避免数字重复使用，需要额外开一个数组 vis 记录每个数字是否已经被用过。

状态记录与还原

和普通递归相比，这里的新技巧是多使用一个数组记录状态：

nums[temp]：记录当前位置选择了哪个数字
vis[i]：记录数字 i 是否已经被使用

每次选择一个数字后，先把它标记为已使用，然后进入下一层递归。

递归结束回来以后，还要把这个数字恢复为未使用，方便下一次枚举。这一步叫“回溯”，也就是把当前选择造成的状态影响撤销掉。

Java 代码

static void test(int temp) {
    if (temp == n + 1) {
        for (int i = 1; i <= n; i++) {
            System.out.print(nums[i]);
        }
        System.out.println();
        return;
    }

    for (int i = 1; i <= n; i++) {
        if (vis[i] != 1) {
            nums[temp] = i;
            vis[i] = 1;
            test(temp + 1);
            vis[i] = 0;
        }
    }
}