回溯算法

思想

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

回溯法解求解问题步骤

1. 针对给定问题，定义问题的解空间树；（这一步非常重要！！）
2. 确定易于搜索的解空间结构；
3. 以深度优先方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索；
4. 用回溯法求解问题，重点是设计问题的解空间树，其解题过程则是深度遍历解空间树的过程。

注：在回溯法中通常会使用到“递归”和“剪枝”

常用的剪枝函数：用约束函数在扩展结点处剪去不满足约束的子树；用限界函数剪去得不到最优解的子树。
回溯法对解空间做深度优先搜索时，有递归回溯和迭代回溯（非递归）两种方法，但一般情况下用递归方法实现回溯法。

模板

回溯法的一般模板，可以如下所示：

demoMethod() {
    //生成回溯结果的存储位置
    Object res = new Object();
    //边界值判定，比如n == 0之类的。
    if() return res;
    //回溯递归函数，先写出来占个坑，参数一会儿加。
    backTrack();
    //返回，程序结束。
    return res;

}

backTrack(...args[]) {   //参数根据题目实际情况来定，数量一般会在4-5个左右
    // 递归的结束条件
    if () {
    }
    //回溯算法的主体，包括前进和回溯，sub是存储结果
    for(){   
    add()  // 1.一个解中的某个元素，进行添加;
   backTrack(index + 1);    // 2.进行深搜，进行到解空间树的下一层
    sub.remove(sub.size() - 1);  // 3.*回溯到解空间树的上一层
    }
    
}

需要注意的是：

• for循环的次数；：在解空间树种每一层有多少种可能的答案，就要循环多少次。
• 以及递归的结束条件：当达到解空间树的叶子节点，即递归的结束条件一般会跟解空间树的深度有关。

具体我们以下面的例子做讲解：

例子

Leetcode上有很多回溯算法问题。这里用一个leetcode上比较经典的题目来做示例
传送门：https://leetcode-cn.com/problems/permutations-ii/

全排列.png

下面将详细介绍一下解题思路：（此思路适用回溯法80%的题目）：
1.定义问题的解空间树，如下图所示；
2.分析发现，在回溯函数中循环的次数应该是每次剩下数组的长度（因为每次都会存储一个值）；如下图中横框框住的元素个数，第一层3种情况；第二层2种情况；第三层1种情况；
3.递归结束条件：当当前的解中的元素经满了（即3个，给定的数组的长度），则跳出本层，回到上层树。

值得注意的是：本题有个要求是，答案不能有重复的。如果不进行剪枝，则会有6个答案，但是如图所示有两处可以剪枝，那剪枝的条件是什么呢？我们发现，只要在每层访问的时候，如果这个节点我们已经访问过了，我们就可以直接跳过，例如：在第一层，第二个的1已经访问过，所以我们可以跳过。因此我们可以在每一层都维护一个已经访问的节点即可。

image.png

解答

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> deque = new LinkedList<>();
        if (nums.length == 0) {
            return res;
        }

        for (int i = 0; i < nums.length; i++) {
            deque.add(nums[i]);
        }

        backTrack(res, new ArrayList<>(), deque, nums.length);
        return res;
    }

    /**
     * 
     * @param res - 存储最后的结果，即返回值
     * @param curList - 存储当前的值
     * @param deque - 解空间树种每一层可能的情况的集合
     * @param length - 递归结束条件的长度，即树的深度
     */
    private static void backTrack(List<List<Integer>> res, List<Integer> curList, List<Integer> deque, int length) {
        if (curList.size() == length) {
            res.add(new ArrayList<>(curList));
        }
        int size = deque.size();
        List<Integer> visited = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            // 剪枝函数
            if (visited.contains(deque.get(i))) {
                continue;
            }
            visited.add(deque.get(i));
            List<Integer> temp = new ArrayList<>(deque);
            curList.add(deque.get(i));
            temp.remove(i);
            backTrack(res, curList, temp, length);
            curList.remove(curList.size() - 1);
        }
    }
}