在算法中，难以理解的莫过于动态规划和回溯算法了，我个人觉得这两种方法基本上没有套路可言，就是没有统一的解题思想，会随着题目变化而变化。

回溯算法其实就是我们常说的深度优先搜索（ DFS ）算法，通过遍历每一个路径获取结果，所以本质上就是一种暴力穷举算法。

而且回溯法也会用到递归。

但是这个暴力穷举的关键点是：在找到符合条件的结果前，先pass其他结果。

如何选择条件递归，是回溯法的关键。

LeetCode经典的回溯法就是全排列问题。

下面来看看这道全排列的题目，看完还是不懂，建议你debug一下。

描述

难度：中等

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/permutations 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

这有点像高中数学，利用数学的思想我们知道这个数组它有 3*2 =6 种不重复的组合。但是要通过算法表示出来，就很脑壳痛了。

我们可以理解为这是个填表游戏。

为了不重复，我们可以这样填：

假如第一个数是1

那么第二个数是2

第三个数只能是3

好了，第一个排列出来了[1,2,3]

那么下一步就是回溯了，最后的3开始，判断前面已经用了1和2，没有数可用了，于是回溯，变成[1,2]，依次再往上回溯变成 [1,3]，打印第二组[1,3,2]，再回溯到[2, ] [3, ]，这样一步步穷举，不符合就回溯，符合就打印。

总结一下这个流程：

1、路径：也就是已经做出的选择。[ ？，？，？] 第一个问号可以是1、2、3

2、选择列表：也就是你当前可以做的选择。[ 1，？，？] 在第一个位置已经填好的条件下，做出当前选择。

3、结束条件：也就是到达决策树底层，无法再做选择的条件。[1，2，3] 结果打成，返回

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

注意：

需要判断数字是否重复，这里提供两个思路：

• contains 方法检验数组是否存在当前数
• 使用数组1和0 记录当前的值是否出现过

题解

public class 全排列46 {
    static List<List<Integer>> res = new LinkedList<>();

    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3};
        System.out.println(permute(nums));
    }

    static List<List<Integer>> permute(int[] nums) {
        LinkedList<Integer> track = new LinkedList<>();
        backtrack(nums, track);
        return res;
    }

    /** 方法一
     * @param nums
     * @param track 虽然是懂了，但是很难解释
     *              [1]的时候，进行回溯，size=1，进入for，包含了1，continue，然后 把 2 加进去
     *              递归，回溯
     *              [1,2]的时候， 进入for循环，i=1. size =2 ，进行循环，包含了 1、2，然后循环把 3 进去
     *              递归，回溯
     *              [1,2,3]的时候，return ，这时候要取消选择了，[1,2],回到上一层
     *              进入for循环，i=2
     *              [1,3]的时候
     */
    static void backtrack(int[] nums, LinkedList<Integer> track) {
        //三位数的排列
        if (track.size() == nums.length) {
            res.add(new LinkedList<>(track));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            //不允许重复
            if (track.contains(nums[i])) {
                continue;
            }
            //做决策，把数字组合
            track.add(nums[i]);
            //进入下一层决策树
            backtrack(nums, track);
            //取消选择，回到上一层
            track.removeLast();
        }
    }
 
    /**方法二
     * 用一个数组记录该数字的下标，判断是否已经用过
     * @param nums
     * @return
     */
    static List<List<Integer>> permute2(int[] nums) {
        List<List<Integer>> res = new LinkedList<>();
        subsets(nums, new LinkedList<Integer>(), res, new int[nums.length]);
        return res;
    }

    static void subsets(int nums[], LinkedList<Integer> track, List<List<Integer>> res, int[] used) {
        if (track.size() == nums.length) {
            res.add(new LinkedList<>(track));
            return;
        }
        //这里只能是从0开始的
        for (int i = 0; i < nums.length; i++) {
            if (used[i] == 1) {
                continue; //防止重复
            }
            //用一个数组记录该数字的下标，判断是否已经用过
            used[i] = 1;
            track.add(nums[i]);
            subsets(nums, track, res, used);
            used[i] = 0;
            track.removeLast();
        }
    }
}