彻底理解回溯法的精要

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

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

问题分析

使用什么方法？

全排列很明显使用回溯法来进行解答

什么是回溯法？

回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

怎么使用回溯法？

运用回溯法解题的关键要素有以下三点：

1. 针对给定的问题，定义问题的解空间；
2. 确定易于搜索的解空间结构；

3. 以深度优先方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。

   什么是深度优先搜索？

   深度优先搜索（缩写DFS）有点类似广度优先搜索，也是对一个连通图进行遍历的算法。它的思想是从一个顶点V0开始，沿着一条路一直走到底，如果发现不能到达目标解，那就返回到上一个节点，然后从另一条路开始走到底，这种尽量往深处走的概念即是深度优先的概念。

代码模板是什么样子的？

void BackTrace(int t) {
    if(t>n)
        Output(x);
    else
    for(int i = f (n, t); i <= g (n, t); i++ ) {
        x[t] = h(i);
        if(Constraint(t) && Bound (t))
        BackTrace(t+1);
    }
}

其中，t表示递归深度，即当前扩展结点在解空间树中的深度；n用来控制递归深度，即解空间树的高度。当t>n时，算法已搜索到一个叶子结点，此时由函数Output(x)对得到的可行解x进行记录或输出处理

用 f(n, t)和 g(n, t)分别表示在当前扩展结点处未搜索过的子树的起始编号和终止编号；h(i)表示在当前扩展结点处x[t]的第i个可选值；函数Constraint(t)和 Bound(t)分别表示当前扩展结点处的约束函数和限界函数。若函数Constraint(t)的返回值为真，则表示当前扩展结点处x[1:t]的取值满足问题的约束条件；否则不满足问题的约束条件。若函数Bound(t)的返回值为真，则表示在当前扩展结点处x[1:t]的取值尚未使目标函数越界，还需由BackTrace(t+1)对其相应的子树做进一步地搜索；否则，在当前扩展结点处x[1:t]的取值已使目标函数越界，可剪去相应的子树。

回溯法的具体实施

class Solution {
    public List<List<Integer>> permute(int[] nums) {
      //LeetCode代码模板  
    }
}

step 1 定义问题的解空间

什么是解空间？

应用回溯法求解问题时，首先应明确定义问题的解空间，该解空间应至少包含问题的一个最优解。例如，对于有n种物品的 0-1 背包问题，其解空间由长度为n的 0-1 向量组成，该解空间包含了对变量的所有可能的0-1 赋值。当n=3时，其解空间是{ (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1) }
在定义了问题的解空间后，还需要将解空间有效地组织起来，使得回溯法能方便地搜索整个解空间，通常将解空间组织成树或图的形式。例如，对于n= 3的0-1 背包问题，其解空间可以用一棵完全二叉树表示，从树根到叶子结点的任意一条路径可表示解空间中的一个元素，如从根结点A到结点J的路径对应于解空间中的一个元素(1, 0, 1)。

定义本题的解空间

全排列问题，因为输入数组的长度为n = nums.length，解空间就是一个森林：

这里需要一个森林的图
假设n=4且nums[]={1,2,3,4}则解空间应该是
第一层：1 2 3 4
第二层：12 13 14 /21 23 24/31 32 34
第三层：123 124/132 134/213 214/231 234/241 243/312 314/.....
第四层：略

确定易于搜索的解空间结构

解空间主要对应的是子集树和排列树，依据题意进行选择。（根据题意画个图，就知道了）

什么是子集树？？？

子集树是一个数学学科词汇，属于函数类，当所给问题是从n个元素的集合S中找出S满足某种性质的子集时，相应的解空间称为子集树。
当所给问题是从n个元素的集合S中找出S满足某种性质的子集时，相应的解空间称为子集树。例如：n个物品的0-1背包问题所相应的解空间是一棵子集树，这类子集树通常有2^n个叶结点，其结点总数为(2^(n+1))-1。遍历子集树的算法通常需O(2^n)计算时间。

什么是排列树？？

当所给问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。排列树通常有n!个叶子节点。因此遍历排列树需要O(n!)的计算时间。

上面已经确定，要将解空间构建成子集树的形式

step 2 回溯法的精髓

回溯的精髓

退回原状态
如何回退是回溯的精髓，什么时候回退
就本题而言，第一躺全排列应该是1->2->3->4 ,当走到最后一步4之后，应该回退一步到1->2->3因为3只有一个分支4，再回退一步到1->2，然后满足了约束函数可以进行下一步1->2->4;
对于本题，回退到方法在于，标记未被访问的数组下标，回退则重制标记
因此可以使用一个visited[]数组，数组的长度为nums.length，被访问则对应的下标标记为true，否则标记为false；

step 3 回溯函数的设计

void BackTrace(int t)只传递一个参数的话显然是无法满足本题的，因为本题包含了一下5个需要传递的参数：

1. visited[] 数组；
2. t 递归深度；
3. List<List<Integer>> output 保存所有解的大容器
4. List<Integer> save 保存解的小容器
5. nums[]原始数据

因此，BackTrace应设计为：

public static void BackTrace( List<Integer> save, List<List<Integer>> out, boolean visited[], int nums[]) {
        if (save.size() == nums.length) {
            out.add(new ArrayList<>(save));
            return;
        } else
            for (int i = 0; i < nums.length; i++) {
                if (visited[i]) continue;
                visited[i] = true;
                save.add(nums[i]);
                BackTrace( save, out, visited, nums);
                save.remove(save.size() - 1);
                visited[i] = false;
            }
    }

怎么写出这段代码需要结合前面的内容反复的思考 =-= 我想了好久才理清楚回溯的思路

回溯法的延伸

子集问题
题目：

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例：
输入: nums = [1,2,3] 输出: [ [3],   [1],   [2],   [1,2,3],   [1,3],   [2,3],   [1,2],   [] ]
从上题中我们可以得出结论，这仍然是一道需要使用回溯法的题目。

解空间与解空间结构

很明显这是一个子集数的解空间结构

假设n=3且nums[]={1,2,3}则解空间应该是
第一层：1 2 3
第二层：12 13/21 23/31 32
第三层：123 132/213 231/312 321/

关键性问题

1. 通过什么方法回退？
2. 约束条件是什么？
3. 去除重复对象

检测重复

检测重复首先想到的会是哈希表HashMap.因此每一次添加都应该在添加之前查找，如果找到重复则不存入；

约束条件是什么

约束条件应该还是当遍历到最后一个元素时退出？

通过什么方法回退？

由于集合的特殊性。不需要回退；

函数的设计：

public static void BackTrack(int t,int[] nums, List<List<Integer>> out, List<Integer> save) {

        out.add(new ArrayList<>(save));

        for (int i = t; i < nums.length; i++) {

            save.add(nums[i]);

            BackTrack(i+1,nums, out, save);

            save.remove(save.size()-1);
        }
    }