開啟掘金成長之旅！這是我參與「掘金日新計劃 · 12 月更文挑戰」的第23天，點選檢視活動詳情。

一，如何理解回溯演算法

深度優先搜尋演算法利用的就是回溯演算法思想，但它除了用來指導像深度優先搜尋這種經典的演算法設計之外，還可以用在很多實際的軟體開發場景中，比如正則表示式匹配、編譯原理中的語法分析等。

除此之外，很多經典的數學問題都可以用回溯演算法解決，比如數獨、八皇后、0-1 揹包、圖的著色、旅行商問題、全排列等等。

回溯的處理思想，有點類似列舉搜尋。暴力列舉所有的解，找到滿足期望的解。為了有規律地列舉所有可能的解，避免遺漏和重複，我們把問題求解的過程分為多個階段。每個階段，我們都會面對一個岔路口，我們先隨意選一條路走，當發現這條路走不通的時候（不符合期望的解），就回退到上一個岔路口，另選一種走法繼續走。

回溯演算法的模板程式碼總結如下：

cpp void backtracking(引數) { if (終止條件) { 存放結果; return; } for (選擇：本層集合中元素（樹中節點孩子的數量就是集合的大小）) { 處理節點; backtracking(路徑，選擇列表); // 遞迴回溯，撤銷處理結果 } }

二，回溯演算法的經典應用

2.1，八皇后問題

有一個 8x8 的棋盤，希望往裡放 8 個棋子（皇后），每個棋子所在的行、列、對角線都不能有另一個棋子。這裡的“對角線”指的是所有的對角線，不只是平分整個棋盤的那兩條對角線。

解決思路：可以把這個問題劃分成 8 個階段，依次將 8 個棋子放到第一行、第二行、第三行……第八行，每一行都有 8 中放法（8 列）。在放置的過程中，我們不停地檢查當前放法，是否滿足要求。如果滿足，則跳到下一行繼續放置棋子；如果不滿足，那就再換一種放法，繼續嘗試。這裡用的是回溯思想，而回溯演算法也非常適合用遞迴程式碼實現。

```cpp // N 皇后問題 leetcode 51 https://leetcode-cn.com/problems/n-queens/ class Solution { private: vector> result; void backtracking(int n, int row, vector& 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& 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> solveNQueens(int n) { result.clear(); std::vector 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 個階段，每個階段對應一個物品怎麼選擇。先對第一個物品進行處理，選擇裝進去或者不裝進去，然後再遞迴地處理剩下的物品。

```cpp int maxW = 0;

// cw 表示當前裝進揹包的物品的重量和，w 表示揹包承載的重量 // items 表示物體的重量陣列，n 表示總的物品個數， i 表示考察到第 i 個物品 int f(int i, int cw, vector 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 個）任意字元，“?” 匹配零個或者一個任意字元。基於以上背景假設，如何用回溯演算法，判斷一個給定的文字，是否和給定的正則表示式匹配？

如果遇到特殊字元的時候，我們就有多種處理方式了，也就是所謂的岔路口，比如 “*” 有多種匹配方案，可以匹配任意個文字串中的字元，我們就先隨意的選擇一種匹配方案，然後繼續考察剩下的字元。如果中途發現無法繼續匹配下去了，我們就回到這個岔路口，重新選擇一種匹配方案，然後再繼續匹配剩下的字元。

```cpp // 暴力遞迴 --> 記憶化 --> 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] 是否匹配。

```python 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 程式碼如下：

```python 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++ 程式碼如下：

```cpp // letcode10 正則表示式匹配

include

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++ 程式碼如下：

```cpp class Solution{ public: bool isMatch(string s, string p){ unordered_map 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 揹包問題、圖的著色、旅行商問題、數獨、全排列、正則表示式匹配等等。

回溯演算法能解決的問題，基本用動態規劃也能解決，其時間複雜度更低，空間複雜度更高，用空間換時間。

深入淺出回溯演算法

一，如何理解回溯演算法

二，回溯演算法的經典應用

2.1，八皇后問題

2.2，0-1 揹包問題

2.3，萬用字元匹配

2.4，leetcode 正則表示式匹配

include

include

三，總結

參考資料