摘要： 回溯的处理思想，有点类似枚举搜索。
本文分享自华为云社区《 深入浅出回溯算法 》，作者：嵌入式视觉。
一，如何理解回溯算法
深度优先搜索算法利用的就是回溯算法思想，但它除了用来指导像深度优先搜索这种经典的算法设计之外，还可以用在很多实际的软件开发场景中，比如正则表达式匹配、编译原理中的语法分析等。
除此之外，很多经典的数学问题都可以用回溯算法解决，比如数独、八皇后、0-1 背包、图的着色、旅行商问题、全排列等等。
回溯的处理思想，有点类似枚举搜索。 暴力枚举所有的解，找到满足期望的解。为了有规律地枚举所有可能的解，避免遗漏和重复，我们把问题求解的过程分为多个阶段。每个阶段，我们都会面对一个岔路口，我们先随意选一条路走，当发现这条路走不通的时候（不符合期望的解），就回退到上一个岔路口，另选一种走法继续走。
回溯算法的模板代码 总结如下：
void backtracking(参数) {
if (终止条件) {
存放结果;
return ;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}
二，回溯算法的经典应用
2.1，八皇后问题
有一个 8x8 的棋盘，希望往里放 8 个棋子（皇后），每个棋子所在的行、列、对角线都不能有另一个棋子。这里的“对角线”指的是所有的对角线，不只是平分整个棋盘的那两条对角线。
解决思路： 可以把这个问题划分成 8 个阶段，依次将 8 个棋子放到第一行、第二行、第三行……第八行，每一行都有 8 中放法（8 列）。在放置的过程中，我们不停地检查当前放法，是否满足要求。如果满足，则跳到下一行继续放置棋子；如果不满足，那就再换一种放法，继续尝试。这里用的是回溯思想，而回溯算法也非常适合用递归代码实现。
// N 皇后问题 leetcode 51 https://leetcode-cn.com/problems/n-queens/
class Solution {
private :
vector <vector< string >> result;
void backtracking( int n, int row, vector< string >& chessboard){
if (row == n) {
result.push_back(chessboard);
return ;
}
for ( int column= 0 ; column < n; column++){ // 每一行都有8中放法
if (isOK(row, column, n, chessboard)){
chessboard[row][column] = ' Q ' ; // 放置皇后
backtracking(n, row+ 1 , chessboard);
chessboard[row][column] = ' . ' ; // 回溯，撤销处理结果
}
}
}
// 判断 row 行 column 列放置皇后是否合适
bool isOK( int row, int column, int n, vector< string >& chessboard){
int leftup = column - 1 ; int rightup = column + 1 ; // 左上角和右上角
for ( int i = row- 1 ; i>= 0 ; i--){ // 逐行网上考察每一行
// 判断第 i 行的 column 列是否有棋子
if (chessboard[i][column] == ' Q ' ) {
return false ;
}
// 考察左上对角线：判断第i行leftup列是否有棋子
if (leftup >= 0 ){
if (chessboard[i][leftup] == ' Q ' ) return false ;
}
// 考察左上对角线：判断第i行rightup列是否有棋子
if (rightup < n){
if (chessboard[i][rightup] == ' Q ' ) return false ;
}
-- leftup;
++ rightup;
}
return true ;
}
public :
vector <vector< string >> solveNQueens( int n) {
result.clear();
std::vector <std:: string > chessboard(n, std:: string (n, ' . ' ));
backtracking(n, 0 , chessboard);
return result;
}
};
2.2，0-1 背包问题
0-1 背包是非常经典的算法问题。0-1 背包问题有很多变体，这里介绍一种比较基础的。我们有一个背包，背包总的承载重量是 W kg。现在我们有 n 个物品， 每个物品的重量不等，并且不可分割 ，即对于每个物品来说，都有两种选择，装进背包或者不装进背包，对于 n 个物品来说，总的装法就有 2^n 种。
我们现在期望选择几件物品，装载到背包中。在不超过背包所能装载重量 W 的前提下，如何让背包中物品的总重量最大？
0-1 背包问题为什么不能用贪心算法求解？
因为不可分割，所以无法判断当前情况下，哪种物品对期望值贡献更大，即不存在当前最优的选择，所以就无法使用贪心算法了。
0-1 背包问题的高效解法是 动态规划 算法，但也可用没那么高效的 回溯 方法求解。我们可以把物品依次排列，整个问题就分解为了 n 个阶段，每个阶段对应一个物品怎么选择。先对第一个物品进行处理，选择装进去或者不装进去，然后再递归地处理剩下的物品。
int maxW = 0 ;
// cw 表示当前装进背包的物品的重量和，w 表示背包承载的重量
// items 表示物体的重量数组，n 表示总的物品个数， i 表示考察到第 i 个物品
int f( int i, int cw, vector< int > items, int n, int w){
// 递归结束条件：cw == w 表示背包已经装满，i==n 表示考察完所有物品
if (cw == w || i == n){
if (cw > maxW) maxW = cw;
return ;
}
f(i + 1 , cw, items, n, w); // 不装
// 剪枝过程，当装入的物品重量大于背包的重量，就不继续执行
if (cw+items[i] <= w){
f(i + 1 , cw+items[i], items, n, w); // 装
}
}
要理解 0-1 背包问题回溯解法的关键在于： 对于一个物品而言，只有两种情况，不装入背包和装入背包两种情况。 对应的就是 f(i+1, cw, items, n, w) 和 f(i+1, cw + items[i], items, n, w) 两个函数。
2.3，通配符匹配
假设正则表达式中只包含 “*” 和 “?” 这两种通配符，并且对这两个通配符的语义稍微做些改变，其中，“*” 匹配任意多个（大于等于 0 个）任意字符，“?” 匹配零个或者一个任意字符。基于以上背景假设，如何用回溯算法，判断一个给定的文本，是否和给定的正则表达式匹配？
如果遇到特殊字符的时候，我们就有多种处理方式了，也就是所谓的岔路口，比如 “*” 有多种匹配方案，可以匹配任意个文本串中的字符，我们就先随意的选择一种匹配方案，然后继续考察剩下的字符。如果中途发现无法继续匹配下去了，我们就回到这个岔路口，重新选择一种匹配方案，然后再继续匹配剩下的字符。
// 暴力递归 --> 记忆化 --> DP --> 状态压缩DP；
class Solution{
private :
bool matched = false ;
void backtracking( int ti, int pj, string text, string pattern){
if (matched) return ;
if (pj == pattern.size()){ // 正则表达式到末尾了
if (ti == text.size())
matched = true ;
return ;
}
// *匹配任意个字符
if (pattern[pj] == ' * ' ){
for ( int k= 0 ; k< text.size()-ti;k++ )
backtracking(ti +k, pj+ 1 , text, pattern);
}
// ?匹配0个或者1个字符
else if (pattern[pj] == ' ? ' ){
backtracking(ti, pj + 1 , text, pattern);
backtracking(ti + 1 , pj+ 1 , text, pattern);
}
// 纯字符匹配才行
else if (ti < pattern.size() && pattern[pj] == text[ti]) {
backtracking(ti + 1 , pj+ 1 , text, pattern);
}
}
public :
bool isMatch( string text, string pattern){
matched = false ;
backtracking( 0 , 0 , text, pattern);
return matched;
}
};
2.4，leetcode 正则表达式匹配
在 leetcode 也有变形题（leetcode10:正则表达式匹配）如下：
其他变形题：leetcode44-通配符匹配给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
‘.’ 匹配任意单个字符 ‘*’ 匹配零个或多个前面的那一个元素所谓匹配，是要涵盖整个字符串 s 的，而不是部分字符串。
方法一：回溯 （分阶段分情况讨论，暴力搜索和剪枝）
首先， 考虑特俗字符只有 '.' 的情况。这种情况会很简单：我们只需要从左到右依次判断 s[i] 和 p[i] 是否匹配。
def isMatch(self,s:str, p:str) -> bool :
""" 字符串 s 和字符规律 p """
if not p: return not s # 边界条件
first_match = s and p[ 0 ] in {s[ 0 ], ' . ' } # 比较第一个字符是否匹配
return first_match and self.isMatch(s[ 1 :], p[ 1 :])
最后， 考虑有 ’*' 的情况，它会出现在 p[1] 的位置，匹配过程中会出现两种情况：
星号代表匹配 0 个前面的元素。如 '##' 和 a*##，这时我们直接忽略 p 的 a*，比较 ## 和 ##， 也就是继续递归比较 s 和 p[i + 2:]； 星号代表匹配一个或多个前面的元素。如 aaab 和 a*b，这时我们将忽略 s 的第一个元素，比较 aab 和 a*b， 也就是继续递归比较 s[i + 1:] 和 p。 （这里默认要检查 s[0] 和 p[0] 是否相等）。Python3 代码如下：
class Solution:
def isMatch(self, s: str, p: str) -> bool :
if not p: return not s
first_match = bool (s and p[ 0 ] in {s[ 0 ], ' . ' }) # 比较第一个字符是否匹配
if len(p) >= 2 and p[ 1 ] == ' * ' :
# * 匹配前面一个字符 0 次或者多次
return self.isMatch(s, p[ 2 :]) or first_match and self.isMatch(s[ 1 :], p)
else :
return first_match and self.isMatch(s[ 1 :], p[ 1 :])
C++ 代码如下：
// letcode10 正则表达式匹配
#include <vector>
#include < string >
using namespace std;
class Solution{
public :
bool isMatch( string s, string p){
// 如果正则串 p 为空字符串，s 也为空，则匹配成功
if (p.empty()) return (s.empty());
// 判断 s 和 p 的首字符是否匹配，注意要先判断 s 不为空
bool match = (!s.empty()) && (s[ 0 ] == p[ 0 ] || p[ 0 ] == ' . ' );
// 如果p的第一个元素的下一个元素是 *，则分别对两种情况进行判断
if (p.size() >= 2 && p[ 1 ] == ' * ' ){
// * 匹配前面一个字符 0 次或者多次
return isMatch(s, p.substr( 2 )) || (match && isMatch(s.substr( 1 ), p));
}
else { // 单个匹配
return match && isMatch(s.substr( 1 ), p.substr( 1 ));
}
}
};
直接递归时间复杂度太大（指数级），可以把之前的递归过程记录下来，用空间换时间。 记忆化递归 的 C++ 代码如下：
class Solution{
public :
bool isMatch( string s, string p){
unordered_map < int , bool > memo;
return backtracking(s, 0 , p, 0 , memo);
}
bool backtracking( string s, int i, string p, int j, unordered_map< int , bool > & memo){
// # 检查 s[i] 是否能被匹配，注意要先判断 s 不为空
bool match = (i < s.size()) && (s[i] == p[j] || p[j] == ' . ' );
if (j >= p.size()) return i >= s.size(); // p 和 s 同时遍历完
int key = i * (p.size() + 1 ) + j; // 哈希键
if (memo.find(key) != memo.end()) // 这个状态之前经历过，可以返回结果
return memo[key];
else if (i == s.size() && j == p.size()) // 如果s和p同时用完，匹配成功
return memo[key] = true ;
else if ((p.size()-j) >= 2 && p[j+ 1 ] == ' * ' ){
// * 匹配前面一个字符 0 次或者多次
if (backtracking(s, i, p, j+ 2 , memo) || match && backtracking(s, i+ 1 , p, j, memo))
return memo[key] = true ;
}
else { // 单个匹配
if (match && backtracking(s, i+ 1 , p, j+ 1 , memo))
return memo[key] = true ;
}
return memo[key] = false ; // 没辙了，匹配失败
}
};
方法二：动态规划法
[ ] 算法思路 [ ] 代码三，总结
回溯算法的思想非常简单，大部分情况下，都是用来解决广义的搜索问题，也就是，从一组可能的解中，选择出一个满足要求的解。回溯算法非常适合用递归来实现，在实现的过程中，剪枝操作是提高回溯效率的一种技巧。利用剪枝，我们并不需要穷举搜索所有的情况，从而提高搜索效率。
尽管回溯算法的原理非常简单，但是却可以解决很多问题，比如我们开头提到的深度优先搜索、八皇后、0-1 背包问题、图的着色、旅行商问题、数独、全排列、正则表达式匹配等等。
回溯算法能解决的问题，基本用动态规划也能解决，其时间复杂度更低，空间复杂度更高，用空间换时间。
参考资料
leetcode 8皇后问题题解 回溯算法：从电影《蝴蝶效应》中学习回溯算法的核心思想 腐烂的橘子题解-回溯和动态规划
点击关注，第一时间了解华为云新鲜技术~
查看更多关于通过4种经典应用，带你熟悉回溯算法的详细内容...