算法通关村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<TreeNode> 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<List<Integer>> combine(int n, int k){ArrayList<List<Integer>> res = new ArrayList<>();if (k <= 0 || n < k){return res;}//用户返回结果ArrayDeque<Integer> path = new ArrayDeque<>();dfs(n, k, 1, path, res);return res;}private void dfs(int n, int k, int startIndex, Deque<Integer> path, List<List<Integer>> res) {//递归终止条件是：path的长度等于kif (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