算法通关村18关 | 透析回溯的模板

回溯有清晰的解题模板，

    void backtracking(参数){
        if (终止条件){
            存放结果;
            return;
        }
        for (选择本层中的集合元素（画成树，就是树节点孩子的大小) {
            处理节点;
            backtracking();
            回溯，撤销处理结果;
        }
    }

1. 从N叉树说起

在回溯之前，先看一下N叉树的遍历问题，我们知道在二叉树中，按照前序遍历的过程如下所示：

    void treeDFS(TreeNode root){
        if (root == null){
            return;
        }
        System.out.println(root.val);
        treeDFS(root.left);
        treeDFS(root.right);
    }
 
    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
    }

假如是N叉树，该如何遍历，将原来的子节点left和right换成list。

    public class TreeNode {
        int val;
        List nodes;
    }
    //N叉树遍历的基本过程
    public static void treeDFS(TreeNode root){
        //递归必须要有终止条件
        if (root == null){
            return;
        }
        //处理节点
        System.out.println(root.val);
        //通过循环，分别遍历N个子树
        for (int i = 0; i < nodes.length; i++) {
            treeDFS("第i个子节点");
        }
    }

2. 为什么有的问题暴力搜索也不行

LeetCode77：给定两个整数n和k，返回1..n中所有可能的k个数的组合。例如，输入n=4，k = 2，则输出：[ [1,2], [1,3], [1,4], [2,3], [2,4], [3,4]。

可以用双重循环暴力搜索

        int n = 4;
        for (int i = 0; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                System.out.println( i + " " + j);
            }
        }

如果n和k都变大，例如k=50，那么50层循环嵌套，时间复杂度就会非常高。

3. 回溯 = 递归 + 局部枚举 + 放下前任

继续研究LeetCode77题目：按照树的思想

n=4时，我们可以选择的n有{1，2，3，4}这四种情况，所以 我们从第一层到第二层的分支有四个，分别表示可以取 1,2,3,4.从左向右取数，取过的不会重复取，第一次取1，集合变为2，3，4，因为k为2，我们只需要再取一个就可以了，分别取2，3，4.

再看k=3，n=5,的树，图中红框标记处，代表一个结果，最后会有空的情况。

从图中发现元素个数时树的宽度，，每个结果的元素个数相当于树的深度（纵向），所以我们说回溯算法时一纵一横。

1. 每次选择都是从类似{1，2，3，4}，{1，2，3，4，5}这样一个序列一个个选，这就是局部枚举，而且越往后，枚举范围越小。
2. 枚举时，我们就是简单的暴力测试而已，一个个验证，能否满足要求，从上图可以看到，这就是N叉树遍历的过程，因此两者代码很相似。
3. 我们再看上图中红色大框起来的部分，这个部分执行过程与n=4，k = 2，的处理完全一样，很明显是个可以递归的子序列。
4. 放下前任，这步还是根据代码解释。

回溯代码

    public List> combine(int n, int k){
        ArrayList> res = new ArrayList<>();
        if (k <= 0 || n < k){
            return res;
        }
        //用户返回结果
        ArrayDeque path = new ArrayDeque<>();
        dfs(n, k, 1, path, res);
        return res;
    }
 
    private void dfs(int n, int k, int startIndex, Deque path, List> res) {
        //递归终止条件是：path的长度等于k
        if (path.size() == k){
            res.add(new ArrayList<>(path));
            return;
        }
        //针对一个结点，遍历可能搜索的起点，其实就是枚举
        for (int i = 0; i <= n; i++) {
            //向路径变量添加一个数，就是上图中的一个树枝的值
            path.addLast(i);
            //搜索起点要加1是为了缩小范围，下一轮递归做准备，因为不允许出现重复元素
            dfs(n,k,i + 1,path,res);
            path.removeLast();
        }
    }

递归中的循环解释：

    for (int i = 0; i <= n; i++) {
        dfs(n,k,i + 1,path,res);
    }

代表图中的四个分支

4. 图解为什么有个撤销操作

主要还是对for循环的理解：

图中解释，我把最外层的for循环成为外for，内层成为内for