递归-全排列问题

递归回溯用于求解子任务重复问题，这里用经典的全排列问题举例说明，如何构建一个算法思路框架。本文用简单的递归回溯和 DFS 搜索两种写法来写下这个问题的代码。（本质上思维都是一样的，只是两种写法适合两种模板。）

递归思想

递归问题这篇文章递归详解 - labuladong 的算法小抄给出了基本定义和一些思维上的指导。

递归的基本思想是某个函数直接或者间接地调用自身，这样就把原问题的求解转换为许多性质相同但是规模更小的子问题。我们只需要关注如何把原问题划分成符合条件的子问题，而不需要去研究这个子问题是如何被解决的。
递归和枚举的区别在于：枚举是横向地把问题划分，然后依次求解子问题，而递归是把问题逐级分解，是纵向的拆分。
递归代码最重要的两个特征：结束条件和自我调用。
自我调用是在解决子问题；
> 结束条件定义了最简子问题的答案。

重叠子问题递归

全排列问题有点像汉诺塔，问题的规模都可以简化为一个模型，拿排列问题来说：

递归思路：划分重复最小子问题：

只有两个数的时候：交换一次、换回来一次（本身）即可
三个数的时候：拿出一个数当头，剩下的两个数重复上一步
四个数的时候：拿出一个数当头，剩下的三个数重复上一步
以此类推……

因此，递归法解决全排列问题就是把模型一层一层简化到 2 个元素，然后交换这两个元素即可。

/**
  *  全排列的递归回溯法
 */
public class FullPermutation {

    public static void main(String[] args) {

        int[] arr = { 1, 2, 3 };

        Permutation(arr, 0, arr.length - 1);

    }

    public static int[] swap(int[] arr, int a, int b) {
        if (a == b) return arr; // 同一位置不需要交换

        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
        return arr;
    }
    // n个数的全排列个数：A(n,n) = n!
    public static void Permutation(int[] arr, int left, int right) {
        if (left == right) {
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
        }
        // 递归思路：划分重复最小子问题
        // 只有两个数的时候：交换一次、换回来一次（本身）即可
        // 三个数的时候：拿出一个数当头，剩下的两个数重复上一步
        // 四个数的时候：拿出一个数当头，剩下的三个数重复上一步
        // 以此类推
        for (int i = left; i <= right; i++) {
            swap(arr, i, left);// 交换i和left位置
            Permutation(arr, left + 1, right); // 拿出上次的left作为头，将left+1 - right继续排列
            swap(arr, i, left);// 换回来（取消决策，回溯）
        }
    }
}

DFS

本文参考回溯算法解题套路框架 - labuladong 的算法小抄这篇文章。

关于回溯问题的解题框架：

解决一个回溯问题，实际上就是一个决策树的遍历过程。

你只需要思考 3 个问题：

路径：也就是已经做出的选择。
选择列表：也就是你当前可以做的选择。
结束条件：也就是到达决策树底层，无法再做选择的条件。

DFS 就是基于以上思路。可以把输入的数组看做一棵决策树，每层都有数组中元素个数个的选择，每次选择后都要在已经选择的元素上标记，下次不再选（已经参与排序），递归调用结束后将该元素访问标记重置，进行下一次选择。

DFS 框架：

搜索过程：每次调用时将元素标记，并写入解空间数组，步数+1，调用结束后把元素标记重置。
搜索边界：当递归进行到最后一层(最后一个元素)时搜索到决策树尽头，此时搜索结束。

代码如下：


public class DFSPermutation {

    public static void main(String[] args) {

        int[] arr = { 1, 2, 3, 4 };

        int[] visited = new int[arr.length]; // 标记数组
        int[] ans = new int[arr.length]; // 解空间临时数组

        dfs(arr, visited, ans, 0);

    }

    /**
     * 深搜 - 全排列问题
     *
     * @param arr
     * @param visited
     * @param ans
     * @param step 步数，相当于树的层数（问题数组有多少个元素 树就有几层）
     */
    public static void dfs(int[] arr, int[] visited, int[] ans, int step) {
        // 没访问过的结点访问
        for (int i = 0; i < arr.length; i++) {
            if (visited[i] == 0) {
                visited[i] = 1;
                ans[step] = arr[i]; // 根据问题的层数(step步数) 写问题的解
                dfs(arr, visited, ans, step + 1);
                visited[i] = 0; // 这步搜索过后把该层元素还原为未访问状态回溯
            }
        }

        if (step == arr.length - 1) {
            for (int i = 0; i < ans.length; i++) {
                System.out.print(ans[i] + " ");
            }
            System.out.println();
        }
    }
}