代码随想录算法训练营第二十四天 | 回溯算法

理论基础

代码随想录原文

什么是回溯法

回溯也可以叫做回溯搜索法，它是一种搜索的方式。

回溯是递归的副产品，只要有递归就会有回溯。

回溯法的效率

虽然回溯法很难，不好理解，但是回溯法并不是什么高效的算法。因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案。如果想让回溯法高效一些，可以加一些剪枝的操作，但也改变不了回溯法就是穷举的本质。

那么既然回溯法并不高效为什么还要用它呢？

因为没得选，一些问题能暴力搜出来就不错了，撑死了再剪枝一下，还没有更高效的解法。

回溯法解决的问题

回溯法，一般可以解决如下几种问题：

• 组合问题：N个数里面按一定规则找出k个数的集合
• 切割问题：一个字符串按一定规则有几种切割方式
• 子集问题：一个N个数的集合里有多少符合条件的子集
• 排列问题：N个数按一定规则全排列，有几种排列方式
• 棋盘问题：N皇后，解数独等等

如何理解回溯法

回溯法解决的问题都可以抽象为树形结构。

因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度。

递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。

回溯法模板

回溯法三部曲，第一步是确定回溯函数的额返回值和参数，第二步是确定回溯函数的终止条件，第三步是去顶回溯搜索的遍历过程，具体如下：

• 回溯函数模板返回值以及参数

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

再来看一下参数，因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来，所以一般是先写逻辑，然后需要什么参数，就填什么参数。

回溯函数的伪代码如下：

void backtracking(参数)

• 回溯函数终止条件

什么时候达到了终止条件，树中就可以看出，一般来说搜到叶子节点了，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。

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

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

• 回溯搜索的遍历过程

在上面我们提到了，回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成了树的深度。

如下图：

注意图中，集合大小和孩子的数量是相等的！

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

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

for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次。

backtracking这里自己调用自己，实现递归。

可以看出，for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果。

回溯算法模板框架如下：

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

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

77. 组合

题目链接：108.将有序数组转换为二叉搜索树

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

文章讲解/视频讲解：https://programmercarl.com/0108.%E5%B0%86%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E8%BD%AC%E6%8D%A2%E4%B8%BA%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html

思路

按照顺序将所有可能的结果加进去，例如对于n = 4, k = 2的题设，可以顺序将[1, 2]、[1, 3]、[1, 4]、[2, 3]、[2, 4]、[3, 4]添加进结果中。

代码的实现按照回溯模板来做：

首先确定backtracking的模板参数，需要传入一个存储当前组合的数组combine，当前遍历到的整数i，题目给定的最大整数n和每个组合的大小k。

回溯的终止条件，当然是combine数组的大小等于k的时候，将combine数组加入最终结果results中，并返回。

遍历过程，对于当前遍历到的整数i，我们对i及之后的数连续遍历，加入combine数组，并递归地对需要添加的下一个数进行处理，具体见代码。

看了卡哥的教程之后，发现这道题可以进行剪枝优化。举一个例子，n = 4, k = 4的话，那么第一层for循环的时候，从元素2开始的遍历都没有意义了。在第二层for循环的时候，从元素3开始的遍历都没有意义了。如下图：

可以优化的点就在于约束每一层for循环的范围。对于我的代码而言，当前遍历的整数为j，从j到n剩余的整数数量为n - j + 1，组合中还需要的元素个数为k - combine.size()，为了保证此次遍历最终能够添加到新的组合，n - j + 1需要大于等于k - combine.size()，即
$$\begin{gathered} n?j+1\ge k?combine.size() \\ j\le n+1?k+combine.size() \end{gathered}$$

C++实现

class Solution {
public:
    vector<vector<int>> results;

    vector<vector<int>> combine(int n, int k) {
        vector<int> combine;
        backtracking(combine, 1, n, k);
        return results;
    }

    void backtracking(vector<int>& combine, int i, int n, int k){
        if(combine.size() == k){
            results.push_back(combine);
            return;
        }
        for(int j = i;j<=n;j++){
            combine.push_back(j);
            backtracking(combine, j + 1, n, k);
            combine.pop_back();
        }
    }
};

// 剪枝的代码
class Solution {
public:
    vector<vector<int>> results;

    vector<vector<int>> combine(int n, int k) {
        vector<int> combine;
        backtracking(combine, 1, n, k);
        return results;
    }

    void backtracking(vector<int>& combine, int i, int n, int k){
        if(combine.size() == k){
            results.push_back(combine);
            return;
        }
        for(int j = i;j<=n + 1 - k + combine.size();j++){
            combine.push_back(j);
            backtracking(combine, j + 1, n, k);
            combine.pop_back();
        }
    }
};