AI summary
type
status
date
slug
summary
category
tags
icon
password

算法框架

回溯算法是什么？解决回溯算法相关的问题有什么技巧？如何学习回溯算法？回溯算法代码是否有规律可循？
其实回溯算法和我们常说的 DFS 算法基本可以认为是同一种算法，它们的细微差异我在 关于 DFS 和回溯算法的若干问题 中有详细解释，本文聚焦回溯算法，不展开。
抽象地说，解决一个回溯问题，实际上就是遍历一棵决策树的过程，树的每个叶子节点存放着一个合法答案。你把整棵树遍历一遍，把叶子节点上的答案都收集起来，就能得到所有的合法答案。
站在回溯树的一个节点上，你只需要思考 3 个问题：
  1. 路径：也就是已经做出的选择。
  1. 选择列表：也就是你当前可以做的选择。
  1. 结束条件：也就是到达决策树底层，无法再做选择的条件。
如果你不理解这三个词语的解释，没关系，我们后面会用「全排列」这个经典的回溯算法问题来帮你理解这些词语是什么意思，现在你先留着印象。
代码方面，回溯算法的框架：
其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」，特别简单。
什么叫做选择和撤销选择呢，这个框架的底层原理是什么呢？下面我们就通过「全排列」这个问题来解开之前的疑惑，详细探究一下其中的奥妙！

46. 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
💡
我们这次讨论的全排列问题不包含重复的数字，包含重复数字的扩展场景我在后文 回溯算法秒杀排列组合子集的九种题型 中讲解。
另外，有些读者之前看过的全排列算法代码可能是那种 swap 交换元素的写法，和我在本文介绍的代码不同。这是回溯算法两种穷举思路，我会在后文 球盒模型：回溯算法穷举的两种视角 讲明白。现在还不适合直接跟你讲那个解法，你照着我的思路学习即可。
我们在高中的时候就做过排列组合的数学题，我们也知道 n 个不重复的数，全排列共有 n! 个。那么我们当时是怎么穷举全排列的呢？
比方说给三个数 [1,2,3]，你肯定不会无规律地乱穷举，一般是这样：
先固定第一位为 1，然后第二位可以是 2，那么第三位只能是 3；然后可以把第二位变成 3，第三位就只能是 2 了；然后就只能变化第一位，变成 2，然后再穷举后两位……
其实这就是回溯算法，我们高中无师自通就会用，或者有的同学直接画出如下这棵回溯树：
notion image
只要从根遍历这棵树，记录路径上的数字，其实就是所有的全排列。我们不妨把这棵树称为回溯算法的「决策树」。
为啥说这是决策树呢，因为你在每个节点上其实都在做决策。
比如说你站在红色节点上，可以选择 1 那条树枝，也可以选择 3 那条树枝。为啥只能在 1 和 3 之中选择呢？因为 2 这个树枝在你身后，这个选择你之前做过了，而全排列是不允许重复使用数字的。
现在可以解答开头的几个名词：[2] 就是「路径」，记录你已经做过的选择；[1,3] 就是「选择列表」，表示你当前可以做出的选择；「结束条件」就是遍历到树的底层叶子节点，这里也就是选择列表为空的时候。
我们定义的 backtrack 函数其实就像一个指针，在这棵树上游走，同时要正确维护每个节点的属性，每当走到树的底层叶子节点，其「路径」就是一个全排列。
再进一步，如何遍历一棵树？这个应该不难吧。各种搜索问题其实都是树的遍历问题，而多叉树的遍历框架就是这样：
注意，这里前序位置和后序位置在 for 循环里面，和 DFS 略有不同。原因用一句话来说就是回溯关注的是路径，DFS 关注的是结点。具体区别见 二叉树系列算法核心纲领。
下面，直接看全排列代码：
我们这里稍微做了些变通，没有显式记录「选择列表」，而是通过 used 数组排除已经存在 track 中的元素，从而推导出当前的选择列表。
至此，我们就通过全排列问题详解了回溯算法的底层原理。当然，这个算法解决全排列不是最高效的，你可能看到有的解法连 used 数组都不使用，通过交换元素达到目的。但是那种解法稍微难理解一些，后文会介绍。
但是必须说明的是，不管怎么优化，都符合回溯框架，而且时间复杂度都不可能低于 ，因为穷举整棵决策树是无法避免的，你最后肯定要穷举出 N! 种全排列结果。
这也是回溯算法的一个特点，不像动态规划存在重叠子问题可以优化，回溯算法就是纯暴力穷举，复杂度一般都很高。

算法实践

你已经学习过 回溯算法核心框架，那么本文就来探讨两道经典算法题：数独游戏和 N 皇后问题。
选择这两个问题，主要是它们的解法思路非常相似，而且它们都是回溯算法在实际生活中的有趣应用。

37. 解数独

编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
  1. 数字 1-9 在每一行只能出现一次。
  1. 数字 1-9 在每一列只能出现一次。
  1. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 '.' 表示。
先不管数独游戏的规则，反正现在就是有 9x9=81 个格子，每个格子都可以填入 1~9 对吧，那总共就有  种填法，把这些解法都穷举一遍，一定可以找到符合规则的答案。
对于这个问题，你心里应该抽象出一棵九叉递归树，共有 81 层，只要心里有了这棵树，就可以套框架写出求解数独游戏的代码了。
但其实， 只是一个非常粗略的估算，实际写代码时，要考虑数独的规则，可以剪枝。
  1. 首先，初始棋盘会给你预先填充一些数字，这些数字是不能改变的，所以这些格子不用穷举，应该从 81 个格子去除。
  1. 另外，数独规则要求每行、每列和每个 3x3 的九宫格内数字都不能重复，所以实际上每个空格子可以填入的数字并不是真的有 9 种选择，而是要根据当前棋盘的状态，去除不合法的数字。
  1. 而且，实际上题目只要求我们寻找一个可行解，所以只要找到一个可行解就可以结束算法了，没必要穷举所有解。
那么这样算下来，穷举的实际复杂度取决于空格子的个数，远低于 ，所以不用担心超时问题。另外，二维数组可以转为一维数组，方便写代码。
讲到这里，我们应该可以发现一个有趣的现象：
按照人类的一般理解，规则越多，问题越难；但是对于计算机来说，规则越多，问题反而越简单。
因为它要穷举嘛，规则越多，越容易剪枝，搜索空间就越小，就越容易找到答案。反之，如果没有任何规则，那就是纯暴力穷举，效率会非常低。
我们对回溯算法的剪枝优化，本质上就是寻找规则，提前排除不合法的选择，从而提高穷举的效率。
能跑，但是超时了，优化方向挺多的，在不改变框架的条件下可以用位运算快速检测数字是否可用。
使用位运算，我们可以用一个整数的9个位来表示这9个数字是否被使用过：
  • 如果第 i 位为 1，表示数字 i 已被使用，否则还未使用
注意，如果定义全局变量，则 found, raw, col, boxes 等元素需要在函数开头重置。如果不想重置，就需要 __init__ 方法。这牵扯到 python 中类属性和实例属性的区别：
  • 类属性 是 所有实例共享 的变量，它们在 类定义时 就已经存在，并且 不会 随着实例的创建而重新分配。
    • 适合需要所有实例共享的数据，例如：常量（PI = 3.14）、计数器（记录创建的实例数量）、缓存（存储共享数据）
  • 实例属性 是 每个实例独有 的变量，它们在 实例创建时 由 __init__ 方法初始化。
    • 适合需要每个实例独立维护的数据，例如：用户信息（name、age）、对象的状态（position、health）

51. N 皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
其实 N 皇后问题和数独游戏的解法思路是一样的，具体有以下差别：
  1. 数独的规则和 N 皇后问题的规则不同，我们需要修改 isValid 函数，判断一个位置是否可以放置皇后。
  1. 题目要求找到 N 皇后问题所有解，而不是仅仅找到一个解。我们需要去除算法提前终止的逻辑，让算法穷举并记录所有的合法解。
这两个问题都比较容易解决，按理说可以直接参照数独游戏的代码实现 N 皇后问题。
但 N 皇后问题相对数独游戏还有一个优化：我们可以以行为单位进行穷举，而不是像数独游戏那样以格子为单位穷举。
举个直观的例子，在数独游戏中，如果我们设置 board[i][j] = 1，接下来呢，要去穷举 board[i][j+1] 了对吧？而对于 N 皇后问题，我们知道每行必然有且只有一个皇后，所以如果我们决定在 board[i] 这一行的某一列放置皇后，那么接下来就不用管 board[i] 这一行了，应该考虑 board[i+1] 这一行的皇后要放在哪里。
所以 N 皇后问题的穷举对象是棋盘中的行，每一行都持有一个皇后，可以选择把皇后放在该行的任意一列。
接下来直接看代码和注释吧：
当然也可以优化，一行内不可能冲突了，列和左右对角线可以用空间换时间：
再简单拓展一下，有可能题目不需要你计算出 N 皇后问题的所有具体结果，而仅仅问你共有几种解法，应该怎么做呢？比如力扣第 52 题「N 皇后 II」。
直接把 res 变量变成 int 类型，每次在 base case 找到一个合法答案的时候递增 res 变量即可。