回溯算法实践 | LianoのBlog

AI summary

type

status

date

slug

summary

括号生成

括号问题可以简单分成两类，一类是前文写过的 括号的合法性判断 ，一类是合法括号的生成。对于括号合法性的判断，主要是借助「栈」这种数据结构，而对于括号的生成，一般都要利用回溯算法进行暴力穷举。

22. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

有关括号问题，你只要记住以下性质，思路就很容易想出来：

一个「合法」括号组合的左括号数量一定等于右括号数量，这个很好理解。

对于一个「合法」的括号字符串组合 p，必然对于任何 0 <= i < len(p) 都有：子串 p[0..i] 中左括号的数量都大于或等于右括号的数量。

如果不跟你说这个性质，可能不太容易发现，但是稍微想一下，其实很容易理解，因为从左往右算的话，肯定是左括号多嘛，到最后左右括号数量相等，说明这个括号组合是合法的。

反之，比如这个括号组合 ))((，前几个子串都是右括号多于左括号，显然不是合法的括号组合。

明白了合法括号的性质，如何把这道题和回溯算法扯上关系呢？

算法输入一个整数 n，让你计算 n 对儿括号能组成几种合法的括号组合，可以改写成如下问题：

现在有 2n 个位置，每个位置可以放置字符 ( 或者 )，组成的所有括号组合中，有多少个是合法的？

这个命题和题目的意思完全是一样的对吧，那么我们先想想如何得到全部 2^(2n) 种组合，然后再根据我们刚才总结出的合法括号组合的性质筛选出合法的组合，不就完事儿了？

那么对于我们的需求，如何打印所有括号组合呢？套一下框架就出来了：

那么，现在能够打印所有括号组合了，如何从它们中筛选出合法的括号组合呢？很简单，加几个条件进行「剪枝」就行了。

对于 2n 个位置，必然有 n 个左括号，n 个右括号，所以我们不是简单的记录穷举位置 i，而是用 left 记录还可以使用多少个左括号，用 right 记录还可以使用多少个右括号，这样就可以通过刚才总结的合法括号规律进行筛选了：

使用列表 append/pop 的效率更高。

这样，我们的算法就完成了，算法的复杂度是多少呢？这个比较难分析，对于递归相关的算法，时间复杂度这样计算（递归次数）*（递归函数本身的时间复杂度）。

backtrack 就是我们的递归函数，其中没有任何 for 循环代码，所以递归函数本身的时间复杂度是 O(1)，但关键是这个函数的递归次数是多少？换句话说，给定一个 n，backtrack 函数递归被调用了多少次？

我们前面怎么分析动态规划算法的递归次数的？主要是看「状态」的个数对吧。其实回溯算法和动态规划的本质都是穷举，只不过动态规划存在「重叠子问题」可以优化，而回溯算法不存在而已。

所以说这里也可以用「状态」这个概念，对于 backtrack 函数，状态有三个，分别是 left, right, track，这三个变量的所有组合个数就是 backtrack 函数的状态个数（调用次数）。

left 和 right 的组合好办，他俩取值就是 0~n 嘛，组合起来也就 n^2 种而已；这个 track 的长度虽然取在 0~2n，但对于每一个长度，它还有指数级的括号组合，这个是不好算的。

说了这么多，就是想让大家知道这个算法的复杂度是指数级，而且不好算，这里就不具体展开了，是 4^n / sqrt(n)，有兴趣的读者可以搜索一下「卡特兰数」相关的知识了解一下这个复杂度是怎么算的。

集合划分

我之前说过回溯算法是笔试中最好用的算法，只要你没什么思路，就用回溯算法暴力求解，即便不能通过所有测试用例，多少能过一点。回溯算法的技巧也不算难，就是穷举一棵决策树的过程，只要在递归之前「做选择」，在递归之后「撤销选择」就行了。

但是，就算暴力穷举，不同的思路也有优劣之分。本文就来看一道非常经典的回溯算法问题，力扣第 698 题「划分为k个相等的子集」。这道题可以帮你更深刻理解回溯算法的思维，得心应手地写出回溯函数。

698. 划分为k个相等的子集

给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。

从数字的角度进行穷举，n 个数字，每个数字有 k 个桶可供选择，所以组合出的结果个数为 k^n，时间复杂度也就是。

从桶的角度进行穷举，每个桶要遍历 n 个数字，对每个数字有「装入」或「不装入」两种选择，所以组合的结果有 2^n 种；而我们有 k 个桶，所以总的时间复杂度为。

当然，这是对最坏复杂度上界的粗略估算，实际的复杂度肯定要好很多，毕竟我们添加了这么多剪枝逻辑。不过，从复杂度的上界已经可以看出第一种思路要慢很多了。

通俗来说，我们应该尽量「少量多次」，就是说宁可多做几次选择（乘法关系），也不要给太大的选择空间（指数关系）；做 n 次「k 选一」仅重复一次，比 n 次「二选一」重复 k 次效率低很多。

先套框架写一下：

这段代码是可以得出正确答案的，但是效率比较低，会超时，我们可以思考一下是否还有优化的空间。

首先，在这个解法中每个桶都可以认为是没有差异的，但是我们的回溯算法却会对它们区别对待，这里就会出现重复计算的情况。

什么意思呢？我们的回溯算法，说到底就是穷举所有可能的组合，然后看是否能找出和为 target 的 k 个桶（子集）。

那么，比如下面这种情况，target = 5，算法会在第一个桶里面装 1, 4：

现在第一个桶装满了，就开始装第二个桶，算法会装入 2, 3：

然后以此类推，对后面的元素进行穷举，凑出若干个和为 5 的桶（子集）。

但问题是，如果最后发现无法凑出和为 target 的 k 个子集，算法会怎么做？

回溯算法会回溯到第一个桶，重新开始穷举，现在它知道第一个桶里装 1, 4 是不可行的，它会尝试把 2, 3 装到第一个桶里。现在第一个桶装满了，就开始装第二个桶，算法会装入 1, 4 。

好，到这里你应该看出来问题了，这种情况其实和之前的那种情况是一样的。也就是说，到这里你其实已经知道不需要再穷举了，必然凑不出来和为 target 的 k 个子集。

但我们的算法还是会傻乎乎地继续穷举，因为在她看来，第一个桶和第二个桶里面装的元素不一样，那这就是两种不一样的情况呀。

那么我们怎么让算法的智商提高，识别出这种情况，避免冗余计算呢？

你注意这两种情况的 visited 数组肯定长得一样，所以 visited 数组可以认为是回溯过程中的「状态」。

所以，我们可以用一个 memo 备忘录，在装满一个桶时记录当前 visited 的状态，如果当前 visited 的状态是曾经出现过的，那就不用再继续穷举，从而起到剪枝避免冗余计算的作用。

有读者肯定会问，visited 是一个布尔数组，怎么作为键进行存储呢？这其实是小问题，比如我们可以把数组转化成字符串，这样就可以作为哈希表的键进行存储了，但是字符串处理效率比较低。

注意题目给的数据规模 nums.length <= 16，也就是说 visited 数组最多也不会超过 16，那么我们完全可以用「位图」的技巧，用一个 int 类型的变量来替代。

这题还是有难度的，回头多复习复习。