回溯

什么是回溯?

回溯可以视为递归的拓展,回溯不是万能的,而且能解决的问题也是非常明确的,例如组合、分割、子集、排列,棋盘等

回溯可以理解为递归的拓展,而代码结构又特别像深度遍历N叉树,因此只要知道递归,理解回溯并不难,难在很多人不理解为什么在递归语句之后要有个“撤销”的操作。

回溯的模板:

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

1.从N叉树说起

首先我们回忆一下二叉树,二叉树有dfs(层序遍历/层次遍历)和bfs,bfs一般借助队列,而dfs一般使用递归或者迭代,这里是前序遍历代码:

 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叉树的dfs:

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

现在发现,回溯和遍历N叉树的代码很相似,继续往下看

2.为什么有的时候暴力搜索不行

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

这里其实也就是高中数学的排列组合,从n个中取出k个,有C kn 中方法,也就是这道题返回结果的总数

具体过程:

  1. 先取一个1,则有[1,2],[1,3],[1,4]三种可能。

  2. 然后取一个2,因为1已经取过了,不再取,则有[2,3],[2,4]两种可能。

  3. 再取一个3,因为1和2都取过了,不再取,则有[3,4]一种可能。

  4. 再取4,因为1,2,3都已经取过了,所以直接返回null。

  5. 所以最终结果就是[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]。

代码实现也非常简单:

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

这样可能不明显,若是我们改变题目的数字:n和k都变大,比如n是200,k是3呢?

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

我们发现,要k个数,就需要k层循环,这样的时间复杂度是恐怖的,暴力搜索很明显无法实现

这就是组合类型问题,除此之外子集、排列、切割、棋盘等方面都有类似的问题,因此我们要找更好的方式。

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

我们继续研究LeetCode77题,我们图示一下上面自己枚举所有答案的过程。

image-20240419204052125

这里的过程是这样的:

  1. n=4时,我们可以选择的n有 {1,2,3,4}这四种情况,所以我们从第一层到第二层的分支有四个,分别表示可以取1,2,3,4。从左向右取数,取过的数,不在重复取
  2. 一次取1,集合变为2,3,4 ,因为k为2,我们只需要再取一个数就可以了,分别取2,3,4,得到集合[1,2] [1,3] [1,4]
  3. 第二次去2,因为1不在,不取自己,只有2,3
  4. 第三次,只有4
  5. 以此类推。。一直到4,就空了

可以发现,图中每次访问到一次叶子节点(图中红框标记处),我们就找到了一个结果。虽然最后一个是空,但是不影响结果。这相当于只需要把从根节点开始每次选择的内容(分支)达到叶子节点时,将其收集起来就是想要的结果。

如果感觉不明显,我们再画一个n=5,k=3的例子:

image-20240419205204601

从图中我们发现元素个数n相当于树的宽度(横向),而每个结果的元素个数k相当于树的深度(纵向)。

所以我们说回溯算法就是一纵一横而已。再分析,我们还发现几个规律:

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

到此,回溯和N叉树就结合起来了,但是还有一个大问题没有解决,回溯一般会有个手动撤销的操作,为什么要这样呢?

我们可以看到,我们收集每个结果不是针对叶子结点的,而是针对树枝的,比如最上层我们首先选了1,下层如果选2,结果就是{1,2},如果下层选了3,结果就是{1,3},依次类推。现在的问题是当我们得到第一个结果{1,2}之后,怎么得到第二个结果{1,3}呢?

可以在得到{1,2}之后将2撤掉,再继续取3,这样就得到了{1,3},同理可以得到{1,4},之后当前层就没有了,我们可以将1撤销,继续从最上层取2继续进行。

这里对应的代码操作就是先将第一个结果放在临时列表path里,得到第一个结果{1,2}之后就将path里的内容放进结果列表resultList中,之后,将path里的2撤销掉, 继续寻找下一个结果{1.3},然后继续将path放入resultLit,然后再撤销继续找。

这里就是标题的:放下前任,继续前进

到这里写出完整的回溯代码:

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        if (k <= 0 || n < k) {
            return res;
        }
        // 用户返回结果
        Deque<Integer> path = new ArrayDeque<>();
        dfs(n, k, 1, path, res);
        return res;
    }

    public void dfs(int n, int k, int startIndex, Deque<Integer> path, List<List<Integer>> res) {
        // 递归终止条件是:path 的长度等于 k
        if (path.size() == k) {
            res.add(new ArrayList<>(path));
            return;
        }
        // 针对一个结点,遍历可能的搜索起点,其实就是枚举
        for (int i = startIndex; i <= n; i++) {
            path.addLast(i);
            // 搜索起点要加1是为了缩小范围,下一轮递归做准备,因为不允许出现重复的元素
            dfs(n, k, i + 1, path, res);
            path.removeLast();
        }
    }
}

上面代码还有个问题要解释一下:startIndex和i是怎么变化的,为什么传给下一层时要加1。
我们可以看到在递归里有个循环

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

看一下图就知道了,这里其实就是枚举,第一次n=4,可以选择1,2,3,4四种情况,所以就有四个分支,for循环就会执行四次:

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

回溯最难理解的部分是这个回溯过程,而且这个过程即使调试也经常会晕:

path.addLast(i);
  dfs(n, k, i + 1, path, res);
  path.removeLast();

这里我们先想一下如果不删除会怎么样?

  for (int i = startIndex; i <= n; i++) {
            path.addLast(i);
            // 搜索起点要加1是为了缩小范围,下一轮递归做准备,因为不允许出现重复的元素
            dfs(n, k, i + 1, path, res);
            path.removeLast();
        }

如果不删除,当在此dfs时,发现长度已经够了,将{1,2,3}添加到结果集当中

我们发现,这里的递归,其实就是递归的每一层,如图中红色1,2,3:

image-20240420092450112

循环的作用很简单,因为是N叉树,所以需要不断对每一个子节点也进行递归,现在理解了过程,再回过头看回溯部分的代码就很好理解了

热身:路径问题

L257二叉树的所有路径

给你一个二叉树的根节点 root ,按 任意顺序 ,返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

示例 1:

img

输入:root = [1,2,3,null,5]
输出:["1->2->5","1->3"]

示例 2:

输入:root = [1]
输出:["1"]

提示:

  • 树中节点的数目在范围 [1, 100]
  • -100 <= Node.val <= 100

这道题之前解法可以先回顾一下:

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        dfs(root, "", res);
        return res;
    }

    private static void dfs(TreeNode root, String path, List<String> res) {
        if (root == null)
            return;
        if (root.left == null && root.right == null) {
            res.add(path + root.val);
        }

        dfs(root.left, path + root.val + "->", res);
        dfs(root.right, path + root.val + "->", res);

    }
}

从回溯的角度来分析,得到第一条路径ABD之后怎么找到第二条路径ABE,这里很明显就是先将D撤销,然后再继续递归就可以了

image-20240420122153156

而这里的回溯,依然是使用一个辅助的集合,来记录每一条路径:

这里我们可以发现依然是回溯的模板,有删除,也有递归

class Solution {
    List<String> res = new ArrayList<>();

    public List<String> binaryTreePaths(TreeNode root) {
        dfs(root, new ArrayList<>());
        return res;
    }

    void dfs(TreeNode node, List<Integer> temp) {
        if (node == null) {
            return;
        }
        temp.add(node.val);
        if (node.left == null && node.right == null) {
            res.add(getRes(temp));
        }
        dfs(node.left, temp);
        dfs(node.right, temp);
        temp.remove(temp.size() - 1);
    }

    String getRes(List<Integer> temp) {
        StringBuilder sb = new StringBuilder();
        sb.append(temp.get(0));
        for (int i = 1; i < temp.size(); i++) {
            sb.append("->").append(temp.get(i));
        }
        return sb.toString();
    }
}

L113 路径总和 II

给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

示例 1:

img

输入:root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出:[[5,4,11,2],[5,8,4,5]]

示例 2:

img

输入:root = [1,2,3], targetSum = 5
输出:[]

示例 3:

输入:root = [1,2], targetSum = 0
输出:[]

提示:

  • 树中节点总数在范围 [0, 5000]
  • -1000 <= Node.val <= 1000
  • -1000 <= targetSum <= 1000

这里的整体过程依然和回溯模板很像,和上一道题几乎很像,但是这里注意要res.add(new …),否则添加的始终是固定数字

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    List<Integer> queue = new LinkedList<>();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        dfs(root, targetSum);
        return res;

    }

    void dfs(TreeNode node, int targetSum) {
        if (node == null) {
            return;
        }
        targetSum -= node.val;
        queue.add(node.val);
        if (node.left == null && node.right == null && targetSum == 0) {
            res.add(new LinkedList<>(queue));
        }
        dfs(node.left, targetSum);
        dfs(node.right, targetSum);
        queue.remove(queue.size() - 1);
    }
}

两道热身总有种意犹未尽的感觉,接下来正式开始做题