回溯之全排列

前言

回溯算法是一种通过逐步构建解决方案来解决问题的方法。全排列问题是其中一个经典的应用之一。它的基本思想是尝试所有可能的排列方式，并逐步构建解决方案，如果发现当前尝试的排列不符合条件，则回溯到上一步，尝试其他可能的选择。

回溯算法本质就是DFS，深搜。

全排列就是可以画成一棵树。有三个概念要清楚。选择列表 路径 结束条件

选择列表指的是在每一步中可以做出的选择，即当前可用的候选元素或者决策。在全排列问题中，选择列表就是尚未被选取的数组元素。

路径指的是当前已经做出的选择，即当前已经形成的部分排列。在全排列问题中，路径就是当前已经选择的一组元素。

结束条件就是路径数组大小和所需排列的数组大小相等

做选择指的是在某一步中从选择列表中选择一个元素，并将其添加到当前的路径中。这个选择可能是选择某个元素作为当前排列的下一个元素，或者是选择某个分支作为当前的搜索方向。在全排列问题中，做选择就是从尚未被选择的元素中选择一个添加到当前排列中。

撤销选择指的是在某一步中，当发现当前的选择导致了不符合要求的情况，或者已经达到了结束条件，需要回溯到上一步的状态，取消之前所做的选择，以便尝试其他的选择。在全排列问题中，撤销选择就是将最近添加到路径中的元素移除，以回到之前的状态。

全排列代码如下（java代码）

	//数字全排列
    public static void backtrack(int[] arr, LinkedList<Integer> track) {
        if (track.size() == arr.length) {
            //可以搜集结果 这里就仅打印看看效果
            System.out.println(track);
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            //可选择的是在路径中未出现过的
            if (track.contains(arr[i])) {
                continue;
            }
            track.add(arr[i]);//做选择
            backtrack(arr, track);
            track.removeLast();//取消选择
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        LinkedList<Integer> track = new LinkedList<>();
        backtrack(arr, track);
    }

结果：

	//字符全排列
    public static void backtrack(char[] arr, LinkedList<Character> track) {
        if (track.size() == arr.length) {
            //可以搜集结果 这里就仅打印看看效果
            System.out.println(track);
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            //可选择的是在路径中未出现过的
            if (track.contains(arr[i])) {
                continue;
            }
            track.add(arr[i]);//做选择
            backtrack(arr, track);
            track.removeLast();//取消选择
        }
    }

    public static void main(String[] args) {
        char[] arr = {'a', 'b', 'c'};
        LinkedList<Character> track = new LinkedList<>();
        backtrack(arr, track);
    }

结果：

小结

全排列问题，其实只要记住了这个思路和套路，重点：明白选择列表 路径 结束条件，基本上要写出来都没问题，万变不离其宗

图参考：https://blog.51cto.com/u_15295608/3008226

觉得有用就点个赞吧，谢谢