LeetCode通关：连刷十四题，回溯算法完全攻略

three-fighter 2021-09-14 原文

刷题路线：https://github.com/youngyangyang04/leetcode-master

大家好，我是被算法题虐到泪流满面的老三，只能靠发发文章给自己打气！

这一节，我们来看看回溯算法。

回溯算法

回溯算法理论基础

什么是回溯

在二叉树的路径问题里，其实我们已经接触到了回溯这种算法。

例如我们在查找二叉树所有路径的时候，查找完一个路径之后，还需要回退，接着找下一个路径。

二叉树所有路径

回溯其实可以说是我们熟悉的DFS，本质上是一种暴力穷举算法，把所有的可能都列举出来，所以回溯并不高效。

这个可能比较抽象，我们举一个例子吧，[1,2,3]三个数可以构成多少种组合呢？

我们的办法就是把所有结果都穷举出来，那怎么穷举呢？可以第一位选1，第二位从[2,3]里选2，第三位从[3]里选3；第二个组合可以第一位选2……

我们把这个选择抽象成一棵树，初步有个印象，这是全排列的问题，后面会刷到。

抽象树

回溯算法模板

回溯算法，可以看作一个树的遍历过程，建议可以去看一下N叉树的遍历，和这个非常类似。

递归有三要素，类似的，回溯同样需要关注三要素：

返回值和参数

回溯算法中函数返回值一般为void。

回溯方法的参数得结合实际问题，但是一般需要一个类似栈的结构来存储每个路径（结果），因为我们一次递归结束之后，节点要回溯到上一个位置。

回溯方法伪代码如下：

void backtrack(参数)

回溯函数终止条件

和递归一样，回溯同样也要有结束条件。

什么时候达到了终止条件，从树的角度来讲，一般来说搜到叶子节点了，对回溯而言，就是找到了满足条件的一个结果。

所以回溯函数终止条件伪代码如下：

if (终止条件) {
    存放结果;
    return;
}

回溯搜索的遍历过程

回溯法一般是在一个序列里做选择，序列的大小构成了树的宽度，递归的深度构成的树的深度。

回溯函数遍历过程伪代码如下：

for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
    处理节点;
    backtracking(路径，选择列表); // 递归
    回溯，撤销处理结果
}

for循环就是遍历序列，可以理解一个节点有多少个孩子，这个for循环就执行多少次。可以理解为横向的遍历。

backtrack就是自己调用自己，可以理解为纵向的遍历。

回溯算法模板

同时递归之后，我们还要撤销之前做的选择。

所以回溯算法模板框架如下：

void backtrack(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtrack(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}