AI summary
type
status
date
slug
summary
category
tags
icon
password

球盒模型：回溯算法穷举的两种视角

在上面这两篇文章中，有读者提出了不同的排列/组合/子集代码写法，比如通过 swap 元素实现全排列，还有没有 for 循环的子集解法代码。我之前不提这些不同的解法，是为了保持这些问题解法形式的一致性，如果在一开始就给大家太多选择，反而容易让人迷糊。
在这篇文章，我不仅会具体介绍之前没有讲到的回溯算法写法，还会告诉你为什么可以那样写，两种写法的本质区别是什么。
💡
先说结论：
  1. 回溯算法穷举的本质思维模式是「球盒模型」，一切回溯算法，皆从此出，别无二法。
  1. 球盒模型，必然有两种穷举视角，分别为「球」的视角穷举和「盒」的视角穷举，对应的，就是两种不同的代码写法。
  1. 从理论上分析，两种穷举视角本质上是一样的。但是涉及到具体的代码实现，两种写法的复杂度可能有优劣之分。你需要选择效率更高的写法。
球盒模型这个词是我随口编的，因为下面我会用「球」和「盒」两种视角来解释，你理解就好。
首先，我们回顾一下以前学过的排列组合知识：
  1. P(n, k)（也有很多书写成 A(n, k)）表示从 n 个不同元素中拿出 k 个元素的排列（Permutation/Arrangement）总数；C(n, k) 表示从 n 个不同元素中拿出 k 个元素的组合（Combination）总数。
  1. 「排列」和「组合」的主要区别在于是否考虑顺序的差异。
  1. 排列、组合总数的计算公式：
notion image

排列

好，现在我问一个问题，这个排列公式 P(n, k) 是如何推导出来的？为了搞清楚这个问题，我需要讲一点组合数学的知识。
排列组合问题的各种变体都可以抽象成「球盒模型」，P(n, k) 就可以抽象成下面这个场景：将 n 个标记了不同序号的球（标号为了体现顺序的差异），放入 k 个标记了不同序号的盒子中（其中 n >= k，每个盒子最终都装有恰好一个球），共有 P(n, k) 种不同的方法。
现在你来，往盒子里放球，你怎么放？其实有两种视角。
首先，你可以站在盒子的视角，每个盒子必然要选择一个球。
这样，第一个盒子可以选择 n 个球中的任意一个，然后你需要让剩下 k - 1 个盒子在 n - 1 个球中选择（这就是子问题 P(n - 1, k - 1)）。
notion image
另外，你也可以站在球的视角，因为并不是每个球都会被装进盒子，所以球的视角分两种情况：
  1. 第一个球可以不装进任何一个盒子，这样的话你就需要将剩下 n - 1 个球放入 k 个盒子。
  1. 第一个球可以装进 k 个盒子中的任意一个，这样的话你就需要将剩下 n - 1 个球放入 k - 1 个盒子。
结合上述两种情况，可以得到：
notion image
你看，两种视角得到两个不同的递归式，但这两个递归式解开的结果都是我们熟知的阶乘形式。至于如何解递归式，涉及数学的内容比较多，这里就不做深入探讨了，有兴趣的读者可以自行学习组合数学相关知识。

组合

了解了排列的推导过程，组合的推导是类似的，也是以球和盒两种视角来做选择，也可以写出两种等价形式。你不妨停在这里思考几分钟，看看你能不能自己发明出组合的推导过程。
下面我来带你推导，组合 C(n, k) 可以抽象成下面这个场景：
因为在组合问题中，我们不在乎元素的顺序，即 {1, 2, 3} 和 {1, 3, 2} 视为同一种组合。所以我们不需要对盒进行编号，可以认为只有一个盒，其容量是 k。
现在你来，往盒子里放球，你怎么放？还是有两种视角。
首先，你可以站在盒子的视角，盒子必然要装 k 个球。
那么第一个球可以选择 n 个球中的任意一个，然后盒子剩余 k - 1 个位置，你需要在剩下的 n - 1 个球中选择（这就是子问题 C(n - 1, k - 1)）。
想到这里，是不是就想列出关系式 C(n, k) = nC(n - 1, k - 1) 了？
不对，这里有个坑，你直接 nC(n - 1, k - 1) 是有重复的，正确的答案应该是 nC(n - 1, k - 1) / k：
notion image
这个除以 k 的操作不太好理解，举例来说就容易看出来了，比方说让你在 [1,2,3,4,5] 中选择 3 个元素，有多少种不同的组合？
你站在盒的视角，盒子容量为 3，开始穷举，第一个位置，你可以选择球 1,2,3,4,5 中的任意一个，比如说选了球 1。
接下来你需要在剩下的元素 2,3,4,5 中选择两个元素，比方说最终你穷举出的组合是 {1,3,4}。
要想知道是否有重复，重复了几次，你就盯紧这个 {1, 3, 4}，它如果有重复，其他组合结果都会重复。
容易发现，如果我第一次选择的是球 3，然后我可能得到 {3, 1, 4}；如果我第一次选择的是球 4，那么我可能得到 {4, 1, 3}；这两种情况都是和 {1, 3, 4} 重复的，因此 {1, 3, 4} 共出现了三次。
另外，你也可以站在球的视角，因为并不是每个球都会被装进盒子，所以球的视角分两种情况：
  1. 第一个球可以不装进盒子，这样的话你就需要将剩下 n - 1 个球放入 k 个盒子。
  1. 第一个球可以装进盒子，这样的话你就需要将剩下 n - 1 个球放入 k - 1 个盒子。
结合上述两种情况，可以得到：
notion image
注意组合和前面排列的区别，因为组合不考虑顺序，所以球选择装进盒子时，只有一种选择，而不是 k 种不同选择，所以 C(n-1, k-1) 不用乘 k。

重新理解全排列问题

就以最基本的元素无重不可复选的全排列为例，我直接把之前的代码 copy 过来：
请问，这个解法是以什么视角进行穷举的？是以球的视角还是盒的视角？
这个代码是以盒的视角进行穷举的，即站在每个位置的角度来选择球，站在 nums 中的每个索引，来选择不同的元素放入这个索引位置。
盒子的第一个位置可以接收 n 个球的任意一个，有 n 种选择，第二个位置可以接收 n - 1 个球的任意一个，有 n - 1 种选择，第三个位置有 n - 2 种选择，以此类推。对应决策树中根节点有 3 个孩子，下一层有 2 个孩子…
上面这段代码，很多读者看了之后就跑来跟我说啊，他看的那个全排列算法是通过 swap 操作来计算的，不需要 used 数组的额外空间，比我讲解的回溯算法框架效率高，怎么怎么的。
是的，我之所以不用那个 swap 的解法，是因为前面那两篇文章的重点在于实践回溯算法「做选择」和「撤销选择」的思维框架，用 used 数组的解法更容易让初学者理解。但从算法效率上说，确实有更高效的代码实现方法。
下面就满足大家的好奇心，跟大家讲讲那个传说中的 swap 的解法，到底是何方神圣。
注意：self.result.append(list(nums)) ，或者是 nums[:] ，因为这里需要拷贝一份新的 nums，而不是用原来的引用（这样后面还会被更改）。
swap 的操作可以理解为更换第一个位置的元素，如下图：
notion image
这个解法也可以正确计算全排列，请你思考，这段代码是以什么视角进行穷举的？是以球的视角还是盒的视角？
很容易能看出来，这里也是盒的视角。那个 start 参数就是当前在选择元素的索引位置，在 start 之前的元素已经心有所属，被其他位置挑走了，所以 start 位置只能从 nums[start..] 中选择元素。
进一步想想，为啥用「盒」的视角，即让索引取选元素的视角，可以用 swap 的方法把 used 数组给优化掉呢？
因为索引容易处理，如果你按顺序从小到大让每个索引去选元素，那么一个 start 变量作为分割线就能把已选元素和未选元素分开。
反过来，如果你让元素去选索引，那就只能依赖额外的数据结构来记录那些索引已经被选过了，这样就会增加额外的空间复杂度。
接下来一个很自然的问题，能不能写出一个以球的视角理解的全排列问题的解法？
当然可以，以球的视角来写全排列的解法代码，就是说 nums 中的每个元素来选择自己想去的索引，对吧。有了这个思路，代码还有何难写。
说实话，虽然挺独特的，但是有点麻烦了，了解即可。

重新理解子集问题

就以最基本的元素无重不可复选的子集为例，我直接把之前的代码 copy 过来：
这个解法是以盒的视角穷举的。
因为刚才讲的全排列问题会考虑顺序的差异，而子集问题不考虑顺序的差异。为了方便理解，我们这里干脆不说「球盒模型」了，说「球桶模型」吧，因为放进盒子的球给人感觉是有顺序的，而丢进桶里的东西给人感觉是无所谓顺序的。
那么，以桶的视角理解，子集问题相当于把 n 个球丢到容量为 n 的桶里，桶可以不装满。
这样，桶的第一个位置可以选择 n 个球中的任意一个，比如选择了球 i，然后桶的第二个位置可以选择球 i 后面的球中的任意一个（通过固定相对顺序保证不会出现重复的子集），以此类推。
当然也可以以球的视角来写，每个球都有两种选择，要么在桶中，要么不在桶中。这样，我们可以写出下面的代码：
决策树如下：
notion image
这也解释了，为什么所有子集（幂集）的数量是 2^n，因为每个元素都有两种选择，要么在子集中，要么不在子集中，所以其递归树就是一棵满二叉树，一共有 2^n 个叶子节点。

回溯 vs DFS

区别在哪

我用最简单的多叉树遍历代码来举例说明回溯算法和 DFS 算法的区别，这是遍历多叉树的代码：
这个多叉树遍历函数，可以变化成回溯算法框架，也可以变化成 DFS 算法框架。
比方我想让他变成回溯算法，那么就是这样：
如果我想让他变成 DFS 算法，那么就是这样：
所以你说它俩有啥本质区别么？其实没有。无非就是按照题目的需求，我们灵活运用罢了。
比方说现在题目让你把多叉树上的每个节点都打印出来，那么你就用 DFS 算法框架呗，如果你非要把这个 print 代码写到 for 循环里面，那么最终打印出来的结果就会漏掉整棵树的根节点。
那么对于排列组合这种经典问题，它们的关注点显然就是在树枝上的，你注意我在前文 回溯算法秒杀所有排列/组合/子集问题 中画的图，都是有深意的：
notion image
图中的数字，为啥画在树枝上而不是节点上？因为你在穷举排列组合的时候，就是在树枝位置做选择（往 track 里面添加的元素），节点中反映的是你此次选择的结果（track 的状态）：
notion image
懂了吧？所以我一般把 DFS 和回溯默认为同一种算法，我们根据题目的需求，灵活选用即可。

backtrack/dfs/traverse 函数可以有返回值吗

理论上你随意，但是我强烈建议，对于 backtrack/dfs/traverse 函数，就作为单纯的遍历函数，请保持 void 类型，不要给它们带返回值。
依据 二叉树系列算法核心纲领 的总结，递归算法主要有两种思维模式，一种是「遍历」的思维，一种是「分解问题」的思维。
分解问题的思维模式大概率是有返回值的，因为要根据子问题的结果来计算当前问题的结果。这种函数的名字我们一般也要取得有意义，比如 int maxDepth(TreeNode root)，一眼就能看出来这个函数的返回值是什么含义。
而遍历的思维模式，我们习惯上就会创建一个名为 backtrack/dfs/traverse 的函数，它本身只起到遍历多叉树的作用，简单明了。
如果再搅合进去一个返回值，意思是你这个函数有特殊的定义？那么请问你的思路到底是遍历还是分解问题？功力不到位的话，很容易把自己绕进去，写着写着自己都不知道这个返回值该咋用了。
我随口编一道简单的题目作为具体的例子：输入一棵二叉树根节点和一个 targetVal，请你在这棵树中找到任意一个值为 targetVal 的节点，如果不存在，返回 null。
这个题很简单吧，可以同时用「遍历」和「分解问题」的思维解决。
如果用「遍历」的思维，可能有读者就会写出这样的代码：
其实这个代码是正确的，但是理解成本就有点高了。
我就会疑惑，你的 traverse 函数为啥会有返回值呢？既然有返回值，你这是分解问题的思路吗？也不太像，并没有见你利用这个返回值，来推导出原问题的结果呀。
仔细看看才明白，原来这个 bool 类型的返回值，是为了在找到一个合法答案后终止递归，减少冗余计算的。
那么我推荐的写法是什么呢？就是各司其职，traverse 函数就起到遍历的作用，不要带返回值，至于是否找到了答案，由外部变量控制。
比方说你可以添加一个 found 外部变量，或者干脆利用 res 变量是否为 null 来判断是否找到了答案：
好了，这样一写就很清楚，我一看就知道你的 traverse 函数仅用来遍历二叉树，具体的算法逻辑，我会去研究前中后序位置上的代码。
所有利用「遍历」思维的递归函数都是相同的道理，建议设置函数名为 traverse/dfs/backtrack，函数不要有返回值，通过外部变量来控制递归的终止。
如果你非要返回一个 bool 类型，也可以，那就按照分解问题的思维模式走，请你把函数的定义写清楚，把函数名字取得有意义，让人一眼就看懂这个函数是干嘛的，以及你到底是怎么使用这个函数的，比如把第一个代码的 traverse 改成 canFind 。
这样，我一眼就理解你的 canFind 函数了：你利用函数的定义去左右子树寻找目标节点，在找到目标节点时加了一点小动作，把目标节点记录到外部变量，作为最终的结果。
当然，这个 canFind 函数其实有点多此一举。既然要用分解问题的思路，那直接用 findTarget 函数来分解问题就好了，直接把目标节点返回回来，何必再定义一个 canFind 函数呢？
上面就是一个简单的例子，阐述了遍历思维和分解问题思维不同的编码风格，本站教程中的代码都遵循这种风格，可以很大程度上减少读者的理解成本。
这种代码风格不是硬性指标，仅是我的个人习惯，但是我强烈建议你在写算法时也参照这种风格，一方面方便面试官理解你的思路，另一方面也是帮助自己理清思路。否则当算法较为复杂时，可能你自己都不知道该怎么用自己写的递归函数了。

base case 和剪枝应该写在哪里

这个问题是啥意思呢，就比如说最简单的二叉树的遍历框架，我一般是这样写的：
那有些读者可能会这样写：
这两种写法当然都可以啦，但是我的一般习惯是，把能提到函数开头的判断逻辑都提到函数开头，因为递归部分是填写前中后序代码的位置，尽量不要和 base case 的逻辑混到一起，否则容易混乱。
比方上面这种写法，你的前中后序位置是哪里？是不是不太清楚？
不过呢，在我优化回溯算法的时候，会习惯把剪枝逻辑放在递归之前，类似这样：
我觉得这样会更清晰嘛，因为你剪枝减掉的就是无效的选择呀，所以放在做选择之前，就很合理。
但大部分情况，把这个剪枝逻辑移到函数开头和 base case 放在一起其实也可以，所以这个就看个人习惯了，只要答案是正确的，你爱咋写咋写吧。