三道题熟练写出回溯算法,记得要看最后的总结~
一、简介
深度优先搜索总是对最近才发现的结点 v 的出发边进行探索,直到该节点的所有出发边都被发现为止。如果还存在着尚未发现的结点,则深度优先搜索将从这些未发现的节点任选一个作为新的源节点,并重复同样的搜索过程。以上过程被不断重复,直至图中的所有节点都被发现。
此处我们先给出伪代码示意:(因为大部分情况我们并不会真的去构造图节点,这样开销太大,而是使用 DFS 深度优先的思想)
1 | bool visited[MAX_VERTEX_NUM]; // 访问标记数组(true为已访,false为未访) |
二、第一个例子:全排列
https://leetcode-cn.com/problems/permutations/
给定一个 没有重复 数字的序列,返回其所有可能的全排列。
对题干不多做分析,是很“朴实”的全排列题。我们可以利用手动分析的办法,画出如下树形图:

很容易发现我们可以利用 DFS 的思想:其中题目要求我们不能填入已经填过的数字,所以应当为给出数据的标记数组,来标记数字是否已经被使用,并动态维护。
1 | void dfs(vector<vector<int>>& res, vector<int>& output, int first, int len, vector<int> tag, vector<int>& nums){ |
使用标记数组来处理填过的数是一个很直观的思路,但是可不可以去掉这个标记数组呢?毕竟标记数组也增加了我们算法的空间复杂度。我们可以将题目给定的 n 个数的数组 nums 划分成左右两个部分,左边的表示已经填过的数,右边表示待填的数,我们在回溯的时候只要动态维护这个数组即可。
1 | void dfs(vector<vector<int>>& res, vector<int>& output, int first, int len){ |
复杂度分析
时间复杂度:$O(n \times n!)$,其中 n 为序列的长度。
算法的复杂度首先受 dfs 的调用次数制约,dfs 的调用次数为 $\sum_{k = 1}^{n}{P(n, k)}$ 次,其中 $P(n, k) = \frac{n!}{(n - k)!} = n (n - 1) … (n - k + 1)$ 式被称作 n 的 k 排列,或者部分排列。
而 $\sum_{k = 1}^{n}{P(n, k)} = n! + \frac{n!}{1!} + \frac{n!}{2!} + \frac{n!}{3!} + … + \frac{n!}{(n-1)!} < 2n! + \frac{n!}{2} + \frac{n!}{2^2} + \frac{n!}{2^{n-2}} < 3n!$。
这说明 dfs 的调用次数是 $O(n!)$ 的。
而对于 dfs 调用的每个叶结点(共 $n!$ 个),我们需要将当前答案使用 $O(n)$ 的时间复制到答案数组中,相乘得时间复杂度为 $O(n \times n!)$。空间复杂度:$O(n)$,其中 n 为序列的长度。除答案数组以外,递归函数在递归过程中需要为每一层递归函数分配栈空间,所以这里需要额外的空间且该空间取决于递归的深度,这里可知递归调用深度为 $O(n)$。
三、第二个例子:组合
https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
![]()
以例子 “23” 字符串为例,数字 2 可以代表字符 a、b、c,数字 3 可以代表字符 d、e、f。凭借朴素的数学知识,我们知道这是一个组合问题,并可以简单地写出答案:
a 开头 | b 开头 | c 开头 |
---|---|---|
ad | bd | cd |
ae | be | ce |
af | bf | cf |
在计算机编程中我们通常使用 DFS 回溯的办法,先将上述过程用图的形式展示:

图的遍历可以用 DFS 解决。因此我们另一个需要解决的是:如何将数字和字符对应(同时需要注意,部分数字对应3个字符,部分数字对应4个字符)。此处我给出的解决方案是:将一个数字对应的字符组成字符串,并用哈希表使数字和字符对应。
以下为代码表示:
1 |
|
接下来我们需要设计 DFS 函数来实现图的深度优先遍历(字符组合)。因为是递归函数,所以有一些必要的参数:phoneMap 哈希表、结果字符串向量 results、给定的数字串输入 digits、正在组合的字符串 result。此外,我们还需要一个位置标记 index 来标记正在组合的位置下标(一般用来控制递归规模)。
1 | void dfs(vector<string>& results, const unordered_map<char, string>& phoneMap, const string& digits, |
DFS 算法有一个很明显的特征:回溯。我们一般先尝试性地走向一个分支,如果分支不合法或分支走到尽头,则需要 “回头走” (回溯)。在本题中即为,我们为一个数字尝试性地分配一个字符,当分支走到尽头时,则撤销之前的一次操作;然后分配下一个字符。
1 | void dfs(vector<string>& results, const unordered_map<char, string>& phoneMap, const string& digits, |
最后将代码进行整合:
1 | void dfs(vector<string>& results, const unordered_map<char, string>& phoneMap, const string& digits, int index, string& result) { |
四、第三个例子 · 单词搜索
https://leetcode-cn.com/problems/word-search/
给定一个二维网格和一个单词,找出该单词是否存在于网格中。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
此处举例:
1 | board = |
当 word = “ABFC” 时,我们用人工观察的方法会从字母“A”开始上下左右地匹配下一个字母,如果中途发现上下左右的字母都无法匹配则回退一个字符。我们可以将上述过程化成一个树状图:

其中向上下左右(UDLR)匹配即为每一个决策节点的分支,向四方搜寻的操作用代码表述为:(体现为当前字符在字符矩阵中的横纵左边的变化)
1 | backtrack(board, word, wordIndex + 1, x - 1, y); // 向上走 |
由于题干要求同一位置的字符只能使用一次,因此需要建立一个同字符矩阵相同大小的访问标记矩阵,每次匹配一位字符就将对应位置标记为已访问;每次回退一步需将对应位置修改为未访问。同时,字符矩阵存在上下左右的边限,因此需要对上下左右访问的合法性进行判断(即不能访问界外数据)。用代码表述为:
1 | char tmp = board[x][y]; // 构建访问标记数组 |
最后对之前代码所涉及的 backtrack 函数进行说明:
bool backtrack(vector<vector<char>>& board, string& word, int wordIndex, int x, int y)
board 和 word 为输入给定的字符矩阵和目标字符串,wordIndex 为当前匹配到的字符的下标,x 和 y 为当前匹配的字符在字符矩阵中的位置(横纵坐标)。完整的 backrack 函数如下:
1 | bool backtrack(vector<vector<char>>& board, string& word, |
上述 backtrack 函数可以解决在同一连通分量中的深度优先搜索,对于不同的连通分量(起始字符位置不同)仅需在循环中调用 backtrack 函数。
1 | bool exist(vector<vector<char>>& board, string word) { |
五、总结
深度优先遍历+回溯算法具有明显的特征,通常具有二维性。可以通过人工推演的方式,画出决策树。一般需要设计两个函数,backtrack 函数(递归)和外层函数。
backtrack 函数一般需要考虑:
- 传递原始数据、标记数据
- 标识并传递递归深度(每次递归深度加深)
- 每次进入更深层次的递归,需要更进标记数据、递归深度;每次回溯需要撤销之前对标记数据的操作
外层函数一般需要考虑:
- 调用 backtrack 递归函数并为顶层递归赋初值