三道题熟练写出回溯算法，记得要看最后的总结~

一、简介

深度优先搜索总是对最近才发现的结点 v 的出发边进行探索，直到该节点的所有出发边都被发现为止。如果还存在着尚未发现的结点，则深度优先搜索将从这些未发现的节点任选一个作为新的源节点，并重复同样的搜索过程。以上过程被不断重复，直至图中的所有节点都被发现。

此处我们先给出伪代码示意：（因为大部分情况我们并不会真的去构造图节点，这样开销太大，而是使用 DFS 深度优先的思想）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool visited[MAX_VERTEX_NUM];  // 访问标记数组（true为已访，false为未访）
void DFSTraverse(Graph G) {
	for (v = 0; v < G.vexnum; v++) visited[v] = false; // 初始化标记数组
	// 依次访问图G的节点，如果是未访问节点，则对该节点执行DFS（作用于非连通图）
	for (v = 0; v < G.vexnum; v++) {  
		if (!visited[v]) DFS(G, v);
	}
}
void DFS(Graph G, int v) { // 从顶点v出发，深度优先遍历图G
	visit(v);           // 访问顶点v
	visited[v] = true;  // 标记v顶点为已访问
	// 依次访问与v相邻的节点，如果节点未访问，则对新的节点执行DFS
	for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighor(G, v, w)) {
		if (!visited[w]) DFS(G, w);
	}
}

二、第一个例子：全排列

https://leetcode-cn.com/problems/permutations/

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

对题干不多做分析，是很“朴实”的全排列题。我们可以利用手动分析的办法，画出如下树形图：

image-20210209121113393

很容易发现我们可以利用 DFS 的思想：其中题目要求我们不能填入已经填过的数字，所以应当为给出数据的标记数组，来标记数字是否已经被使用，并动态维护。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void dfs(vector<vector<int>>& res, vector<int>& output, int first, int len, vector<int> tag, vector<int>& nums){
    // 所有数都填完了
    if (first == len) {
        res.push_back(output);
        return;
    }
    for (int i = first; i < len; i++) {
        for (int j = 0; j < len; j++) {
            if (tag[j] != 1) {  // 如果是未访问数
                tag[j] = 1;
                output.push_back(nums[j]);
                dfs(res, output, first + 1, len, tag, nums);
                // 撤回标记和结果数组
                tag[j] = 0;  
                output.pop_back();
            }
        }
    }
}
vector<vector<int>> permute(vector<int>& nums) {
    int len = nums.size();
    vector<vector<int> > res;
    vector<int> tag(len);  // 访问标记数组
    vector<int> output(0);
    dfs(res, output, 0, nums.size(), tag, nums);
    return res;
}

使用标记数组来处理填过的数是一个很直观的思路，但是可不可以去掉这个标记数组呢？毕竟标记数组也增加了我们算法的空间复杂度。我们可以将题目给定的 n 个数的数组 nums 划分成左右两个部分，左边的表示已经填过的数，右边表示待填的数，我们在回溯的时候只要动态维护这个数组即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void dfs(vector<vector<int>>& res, vector<int>& output, int first, int len){
    // 所有数都填完了
    if (first == len) {
        res.emplace_back(output);
        return;
    }
    for (int i = first; i < len; ++i) {
        // 动态维护数组
        swap(output[i], output[first]);
        // 继续递归填下一个数
        dfs(res, output, first + 1, len);
        // 撤销操作
        swap(output[i], output[first]);
    }
}
vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int> > res;
    dfs(res, nums, 0, nums.size());
    return res;
}

复杂度分析

  • 时间复杂度：$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 不对应任何字母。

image-20210210090811994

以例子 “23” 字符串为例，数字 2 可以代表字符 a、b、c，数字 3 可以代表字符 d、e、f。凭借朴素的数学知识，我们知道这是一个组合问题，并可以简单地写出答案：

a 开头 b 开头 c 开头
ad bd cd
ae be ce
af bf cf

在计算机编程中我们通常使用 DFS 回溯的办法，先将上述过程用图的形式展示：

image-20210210092424586

图的遍历可以用 DFS 解决。因此我们另一个需要解决的是：如何将数字和字符对应（同时需要注意，部分数字对应3个字符，部分数字对应4个字符）。此处我给出的解决方案是：将一个数字对应的字符组成字符串，并用哈希表使数字和字符对应。

以下为代码表示：

1
2
3
4
5
6
7
8
9
10
11
#include <unordered_map>  // unordered_map 对应的头文件
unordered_map<char, string> phoneMap{
    {'2', "abc"},
    {'3', "def"},
    {'4', "ghi"},
    {'5', "jkl"},
    {'6', "mno"},
    {'7', "pqrs"},
    {'8', "tuv"},
    {'9', "wxyz"}
};

接下来我们需要设计 DFS 函数来实现图的深度优先遍历（字符组合）。因为是递归函数，所以有一些必要的参数：phoneMap 哈希表、结果字符串向量 results、给定的数字串输入 digits、正在组合的字符串 result。此外，我们还需要一个位置标记 index 来标记正在组合的位置下标（一般用来控制递归规模）。

1
2
void dfs(vector<string>& results, const unordered_map<char, string>& phoneMap, const string& digits, 
         int index, string& result)

DFS 算法有一个很明显的特征：回溯。我们一般先尝试性地走向一个分支，如果分支不合法或分支走到尽头，则需要 “回头走” （回溯）。在本题中即为，我们为一个数字尝试性地分配一个字符，当分支走到尽头时，则撤销之前的一次操作；然后分配下一个字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void dfs(vector<string>& results, const unordered_map<char, string>& phoneMap, const string& digits, 
         int index, string& result) {
    // 递归最小规模（完成所有数字的组合）
    if (index == digits.length()) {
        results.push_back(result);
    } else {
        char digit = digits[index];
        const string& letters = phoneMap.at(digit);  // 获取当前数字对应的字符串
        for (const char& letter: letters) {
            result.push_back(letter); 
            dfs(results, phoneMap, digits, index + 1, result);
            result.pop_back(); // 回溯
        }
    }
}

最后将代码进行整合：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
void dfs(vector<string>& results, const unordered_map<char, string>& phoneMap, const string& digits, int index, string& result) {
    if (index == digits.length()) {
        results.push_back(result);
    } else {
        char digit = digits[index];
        const string& letters = phoneMap.at(digit);
        for (const char& letter: letters) {
            result.push_back(letter);
            dfs(results, phoneMap, digits, index + 1, result);
            result.pop_back();
        }
    }
}

vector<string> letterCombinations(string digits) {
    vector<string> results;
    if (digits.empty()) {   // 判空
        return results;
    }
    unordered_map<char, string> phoneMap{
            {'2', "abc"},
            {'3', "def"},
            {'4', "ghi"},
            {'5', "jkl"},
            {'6', "mno"},
            {'7', "pqrs"},
            {'8', "tuv"},
            {'9', "wxyz"}
    };
    string result;
    dfs(results, phoneMap, digits, 0, result);   // index从0开始
    return results;
}

四、第三个例子 · 单词搜索

https://leetcode-cn.com/problems/word-search/

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

此处举例：

1
2
3
4
5
6
board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

当 word = “ABFC” 时，我们用人工观察的方法会从字母“A”开始上下左右地匹配下一个字母，如果中途发现上下左右的字母都无法匹配则回退一个字符。我们可以将上述过程化成一个树状图：

image-20210215151124924

其中向上下左右（UDLR）匹配即为每一个决策节点的分支，向四方搜寻的操作用代码表述为：（体现为当前字符在字符矩阵中的横纵左边的变化）

1
2
3
4
backtrack(board, word, wordIndex + 1, x - 1, y);  // 向上走
backtrack(board, word, wordIndex + 1, x + 1, y);  // 向下走
backtrack(board, word, wordIndex + 1, x, y - 1);  // 向左走
backtrack(board, word, wordIndex + 1, x, y + 1);  // 向右走

由于题干要求同一位置的字符只能使用一次，因此需要建立一个同字符矩阵相同大小的访问标记矩阵，每次匹配一位字符就将对应位置标记为已访问；每次回退一步需将对应位置修改为未访问。同时，字符矩阵存在上下左右的边限，因此需要对上下左右访问的合法性进行判断（即不能访问界外数据）。用代码表述为：

1
2
3
4
5
6
7
8
9
char tmp = board[x][y];  // 构建访问标记数组
board[x][y] = 0;
if((x > 0 && backtrack(board, word, wordIndex, x - 1, y)) // 往上走
   || (y > 0 && backtrack(board, word, wordIndex, x, y - 1)) // 往左走
   || (x < board.size() - 1 && backtrack(board, word, wordIndex, x + 1, y)) // 往下走
   || (y < board[0].size() - 1 && backtrack(board, word, wordIndex, x, y + 1))){ // 往右走
    return  true; // 其中一条能走通，就算成功
}
board[x][y] = tmp; // 如果都不通，则回溯上一状态

最后对之前代码所涉及的 backtrack 函数进行说明：

bool backtrack(vector<vector<char>>& board, string& word, int wordIndex, int x, int y)

board 和 word 为输入给定的字符矩阵和目标字符串，wordIndex 为当前匹配到的字符的下标，x 和 y 为当前匹配的字符在字符矩阵中的位置（横纵坐标）。完整的 backrack 函数如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool backtrack(vector<vector<char>>& board, string& word, 
               int wordIndex, int x, int y){
    // 当前位的字母不相等，此路不通
    if( board[x][y] != word[wordIndex]) return false;
    // 最后一个字母也相等, 返回成功
    if(word.size() - 1  == wordIndex) return true;
    char tmp = board[x][y]; 
    board[x][y] = 0;
    if((x > 0 && backtrack(board, word, wordIndex + 1, x - 1, y)) // 往上走
       || (y > 0 && backtrack(board, word, wordIndex + 1, x, y - 1)) // 往左走
       || (x < board.size() - 1 && backtrack(board, word, wordIndex + 1, x + 1, y)) // 往下走
       || (y < board[0].size() - 1 && backtrack(board, word, wordIndex + 1, x, y + 1))){ // 往右走
        return  true; // 其中一条能走通，就算成功
    }
    board[x][y] = tmp; // 如果都不通，则回溯上一状态
    return false;
}

上述 backtrack 函数可以解决在同一连通分量中的深度优先搜索，对于不同的连通分量（起始字符位置不同）仅需在循环中调用 backtrack 函数。

1
2
3
4
5
6
7
8
9
bool exist(vector<vector<char>>& board, string word) {
    for(int i = 0; i < board.size(); i++){
        for(int j = 0; j < board[0].size(); j++){
            // 从二维表格的每一个格子出发
            if(backtrack(board, word, 0, i , j)) return true;
        }
    }
    return false;
}

五、总结

​ 深度优先遍历+回溯算法具有明显的特征，通常具有二维性。可以通过人工推演的方式，画出决策树。一般需要设计两个函数，backtrack 函数（递归）和外层函数。

  • backtrack 函数一般需要考虑：

    • 传递原始数据、标记数据
    • 标识并传递递归深度（每次递归深度加深）
    • 每次进入更深层次的递归，需要更进标记数据、递归深度；每次回溯需要撤销之前对标记数据的操作

  • 外层函数一般需要考虑：

    • 调用 backtrack 递归函数并为顶层递归赋初值