回溯演算法完全指南：以《Hello 算法》前序走訪為例掌握嘗試、回退與剪枝

回溯演算法完全指南：以《Hello 算法》前序走訪為例掌握嘗試、回退與剪枝

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo

回溯演算法（backtracking algorithm）是解決搜尋問題、約束滿足問題與組合最佳化問題的經典窮舉策略，其核心是「從初始狀態出發，暴力搜尋所有可能解，遇正確解則記錄，直到找到解或窮盡所有選擇」。本文以《Hello 算法》繁體中文版 backtracking_algorithm.md 為主體，結合倉庫內 Python 與 C++ 的完整可執行範例，從「前序走訪二元樹找節點」的直觀案例出發，逐步拆解回溯的三個核心機制——嘗試、回退與剪枝，並提煉出可套用於全排列、子集和、N 皇后等問題的通用框架程式碼。讀完本文，你將掌握回溯演算法的標準解題模板、常用術語體系，以及判斷何時應該（或不應該）使用回溯的工程視角。

回溯演算法的本質：深度優先搜尋解空間

回溯演算法通常採用深度優先搜尋（DFS）來走訪解空間。在《Hello 算法》二元樹章節中，前序、中序、後序走訪都屬於深度優先搜尋。本文利用前序走訪構造一個最簡單的回溯問題，逐步理解其工作原理。

!!! question "例題一"

給定一棵二元樹，搜尋並記錄所有值為 $7$ 的節點，請返回節點串列。

解題思路非常直接：前序走訪這棵樹，判斷當前節點的值是否為 $7$，若是則將該節點加入結果串列res。對應的完整可執行實現在 preorder_traversal_i_compact.py：

def pre_order(root: TreeNode): """前序走訪：例題一""" if root is None: return if root.val == 7: # 記錄解 res.append(root) pre_order(root.left) pre_order(root.right)

測試資料為list_to_tree([1, 7, 3, 4, 5, 6, 7])，即根節點值為 $1$，左子樹含節點 $7$，右子樹含節點 $3$ 與另一值為 $7$ 的節點。執行程式後輸出「所有值為 7 的節點」，驗證了前序走訪能依序命中兩個目標節點。搜尋過程如下圖所示：

從這個例子可以看出，回溯演算法的搜尋本質就是沿著樹的深度一路「走到底」，在每個節點處判斷是否構成解——這正是深度優先搜尋的典型形態。

嘗試與回退：前進與撤銷的逆向操作

之所以稱之為「回溯」演算法，是因為它在搜尋解空間時會採用「嘗試」與「回退」的策略。當演算法在某個狀態無法繼續前進、或無法得到滿足條件的解時，它會撤銷上一步的選擇，退回到之前的狀態，再嘗試其他可能的選擇。

對例題一而言，訪問每個節點都代表一次「嘗試」，而越過葉節點或返回父節點的return則表示「回退」。但回退並不僅僅包括函式返回——為了說明這點，我們對例題一稍作拓展。

!!! question "例題二"

在二元樹中搜索所有值為 $7$ 的節點，**請返回根節點到這些節點的路徑**。

在例題一程式碼的基礎上，需要藉助一個串列path記錄訪問過的節點路徑。當訪問到值為 $7$ 的節點時，複製path並新增進結果串列res。完整實現在 preorder_traversal_ii_compact.py：

def pre_order(root: TreeNode): """前序走訪：例題二""" if root is None: return # 嘗試 path.append(root) if root.val == 7: # 記錄解 res.append(list(path)) pre_order(root.left) pre_order(root.right) # 回退 path.pop()

關鍵點在於：

• 嘗試：透過path.append(root)將當前節點加入路徑，記錄「走過的路」；
• 記錄解：命中值為 $7$ 的節點時，用res.append(list(path))複製一份路徑存入結果（必須複製，否則後續path.pop()會污染已記錄的解）；
• 回退：在遞迴返回前執行path.pop()，將該節點從path中彈出，以恢復本次嘗試之前的狀態。

觀察下面的逐步動畫，可以將「嘗試」與「回退」理解為「前進」與「撤銷」——兩個操作互為逆向：

=== "<1>"=== "<2>"=== "<3>"=== "<4>"=== "<5>"=== "<6>"=== "<7>"=== "<8>"=== "<9>"=== "<10>"=== "<11>"

「嘗試」與「回退」成對出現、方向相反，這是回溯演算法區別於普通深度優先搜尋的標誌性結構：任何一次append都必須有對應的pop與之匹配，否則狀態無法正確還原，解空間的搜尋就會被污染。

剪枝：用約束條件砍掉無效分支

複雜的回溯問題通常包含一個或多個約束條件，約束條件通常可用於「剪枝」（pruning）。

!!! question "例題三"

在二元樹中搜索所有值為 $7$ 的節點，請返回根節點到這些節點的路徑，**並要求路徑中不包含值為 $3$ 的節點**。

為了滿足約束條件，需要新增剪枝操作：在搜尋過程中，若遇到值為 $3$ 的節點，則提前返回，不再繼續搜尋。完整實現在 preorder_traversal_iii_compact.py：

def pre_order(root: TreeNode): """前序走訪：例題三""" # 剪枝 if root is None or root.val == 3: return # 嘗試 path.append(root) if root.val == 7: # 記錄解 res.append(list(path)) pre_order(root.left) pre_order(root.right) # 回退 path.pop()

與例題二相比，僅在進入節點前多了一行if root is None or root.val == 3: return，便能在第一時間跳過值為 $3$ 的節點及其整個子樹。「剪枝」是一個非常形象的名詞：如下圖所示，在搜尋過程中，我們「剪掉」了不滿足約束條件的搜尋分支，避免許多無意義的嘗試，從而提高搜尋效率：

剪枝的位置與寫法直接影響效率：剪枝越早（越靠近搜尋樹的頂部），被跳過的子樹越大，節省的計算量越可觀。在後續的全排列、子集和、N 皇后問題中，剪枝都是控制時間複雜度的關鍵手段。

框架程式碼：把「嘗試、回退、剪枝」提煉成通用模板

例題一至三的實現高度依賴二元樹的前序走訪結構。接下來，將回溯的主體框架——嘗試、回退、剪枝——提煉出來，提升程式碼的通用性。框架中三個核心參數的含義是：

• state：問題的當前狀態（例如目前已訪問的節點路徑）；
• choices：當前狀態下可以做出的選擇（例如當前節點的左右子節點）；
• res：結果集合，用於收集所有解。

《Hello 算法》在 backtracking_algorithm.md 中給出了 Python、C++、Java、C#、Go、Swift、JS、TS、Dart、Rust、C、Kotlin、Ruby 共 13 種語言的框架實現，下面選取代表性的幾種：

=== "Python"

```python def backtrack(state: State, choices: list[choice], res: list[state]): """回溯演算法框架""" # 判斷是否為解 if is_solution(state): # 記錄解 record_solution(state, res) # 不再繼續搜尋 return # 走訪所有選擇 for choice in choices: # 剪枝：判斷選擇是否合法 if is_valid(state, choice): # 嘗試：做出選擇，更新狀態 make_choice(state, choice) backtrack(state, choices, res) # 回退：撤銷選擇，恢復到之前的狀態 undo_choice(state, choice) ```

=== "C++"

```cpp /* 回溯演算法框架 */ void backtrack(State *state, vector<Choice *> &choices, vector<State *> &res) { // 判斷是否為解 if (isSolution(state)) { // 記錄解 recordSolution(state, res); // 不再繼續搜尋 return; } // 走訪所有選擇 for (Choice choice : choices) { // 剪枝：判斷選擇是否合法 if (isValid(state, choice)) { // 嘗試：做出選擇，更新狀態 makeChoice(state, choice); backtrack(state, choices, res); // 回退：撤銷選擇，恢復到之前的狀態 undoChoice(state, choice); } } } ```

=== "Java"

```java /* 回溯演算法框架 */ void backtrack(State state, List<Choice> choices, List<State> res) { // 判斷是否為解 if (isSolution(state)) { // 記錄解 recordSolution(state, res); // 不再繼續搜尋 return; } // 走訪所有選擇 for (Choice choice : choices) { // 剪枝：判斷選擇是否合法 if (isValid(state, choice)) { // 嘗試：做出選擇，更新狀態 makeChoice(state, choice); backtrack(state, choices, res); // 回退：撤銷選擇，恢復到之前的狀態 undoChoice(state, choice); } } } ```

框架中五個待實現的「鉤子函式」分工明確，是套用模板時唯一需要針對具體問題填寫的部分：

函式	職責	例題三中的實現
is_solution(state)	判斷當前狀態是否為解	state[-1].val == 7
record_solution(state, res)	將解存入結果集合	res.append(list(state))
is_valid(state, choice)	判斷某選擇是否合法（剪枝條件）	choice is not None and choice.val != 3
make_choice(state, choice)	做出選擇、更新狀態（嘗試）	state.append(choice)
undo_choice(state, choice)	撤銷選擇、恢復狀態（回退）	state.pop()

接下來基於框架程式碼重新解決例題三。狀態state為節點走訪路徑，選擇choices為當前節點的左子節點和右子節點，結果res是路徑串列。完整實現在 preorder_traversal_iii_template.py：

def backtrack( state: list[TreeNode], choices: list[TreeNode], res: list[list[TreeNode]] ): """回溯演算法：例題三""" # 檢查是否為解 if is_solution(state): # 記錄解 record_solution(state, res) # 走訪所有選擇 for choice in choices: # 剪枝：檢查選擇是否合法 if is_valid(state, choice): # 嘗試：做出選擇，更新狀態 make_choice(state, choice) # 進行下一輪選擇 backtrack(state, [choice.left, choice.right], res) # 回退：撤銷選擇，恢復到之前的狀態 undo_choice(state, choice)

一個容易被忽略的細節：是否保留return

注意例題三的框架實現中，record_solution之後沒有return。根據題意，找到值為 $7$ 的節點後應該繼續搜尋其子樹（因為路徑中的其他節點仍可能構成新的解），因此必須刪除「記錄解之後立即返回」的語句。下圖對比了保留與刪除return語句的搜尋過程差異：

這個細節說明：「是否為解」與「是否繼續搜尋」是兩個獨立的決策。若問題要求找到一個解即可（如求解唯一可行方案），可以提前返回；若要求所有解（如找出全部路徑），則必須繼續走訪。相比基於前序走訪的直接實現，基於框架的程式碼雖然顯得囉唆，但通用性更好——許多回溯問題只需定義state、choices並實現上述五個函式即可在該框架下解決。

常用術語：解、約束、狀態、嘗試、回退、剪枝

為更清晰地分析演算法問題，回溯演算法中常用術語的含義及其在例題三中的對應示例總結如下：

名詞	定義	例題三中的示例
解（solution）	解是滿足問題特定條件的答案，可能有一個或多個	根節點到節點 $7$ 的滿足約束條件的所有路徑
約束條件（constraint）	約束條件是限制解的可行性的條件，通常用於剪枝	路徑中不包含節點 $3$
狀態（state）	狀態表示問題在某一時刻的情況，包括已經做出的選擇	當前已訪問的節點路徑，即path節點串列
嘗試（attempt）	嘗試是根據可用選擇探索解空間的過程，包括做出選擇、更新狀態、檢查是否為解	遞迴訪問左（右）子節點，將節點加入path，判斷節點的值是否為 $7$
回退（backtracking）	回退指遇到不滿足約束條件的狀態時，撤銷前面做出的選擇，回到上一個狀態	越過葉節點、結束節點訪問、遇到值為 $3$ 的節點時終止搜尋，函式返回
剪枝（pruning）	剪枝是根據問題特性和約束條件避免無意義搜尋路徑的方法，可提高搜尋效率	遇到值為 $3$ 的節點時不再繼續搜尋

!!! tip

問題、解、狀態等概念是通用的，在分治、回溯、動態規劃、貪婪等演算法中都有涉及。掌握這套術語體系，有助於在不同演算法之間遷移思考方式。

優點與侷限性：何時該用、何時不該用回溯

回溯演算法本質上是一種深度優先搜尋演算法，嘗試所有可能的解決方案直到找到滿足條件的解。優點在於能夠找到所有可能的解決方案，而且在合理的剪枝操作下具有很高的效率。

然而在處理大規模或複雜問題時，回溯演算法的執行效率可能難以接受：

• 時間：回溯通常需要走訪狀態空間的所有可能，時間複雜度可達指數階或階乘階；
• 空間：遞迴呼叫中需要儲存當前狀態（如路徑、用於剪枝的輔助變數等），當深度很大時，空間需求可能變得很大。

即便如此，回溯演算法仍然是某些搜尋問題和約束滿足問題的最佳解決方案——當無法預測哪些選擇能生成有效解時，必須對所有可能選擇進行走訪。在這種情況下，關鍵是如何最佳化效率，常見方法有兩種：

• 剪枝：避免搜尋肯定不會產生解的路徑，節省時間與空間；
• 啟發式搜尋：在搜尋過程中引入策略或估計值，優先搜尋最可能產生有效解的路徑。

回溯典型例題：三大問題類別與實戰去向

回溯演算法可用於解決許多搜尋問題、約束滿足問題和組合最佳化問題，本節同時列出《Hello 算法》倉庫中對應的可執行實作路徑，方便讀者邊讀邊跑。

搜尋問題——目標是找到滿足特定條件的解決方案：

• 全排列問題：給定一個集合，求出其所有可能的排列組合。實現見 permutations_i.py（無重複元素）與 permutations_ii.py（含重複元素，需用雜湊集合剪枝）；
• 子集和問題：給定一個集合和一個目標和，找到集合中所有和為目標和的子集。實現見 subset_sum_i_naive.py、subset_sum_i.py 與 subset_sum_ii.py；
• 河內塔問題：給定三根柱子和一系列大小不同的圓盤，要求將所有圓盤從一根柱子移到另一根柱子，每次只能移動一個圓盤，且不能將大圓盤放在小圓盤上。

約束滿足問題——目標是找到滿足所有約束條件的解：

• N 皇后：在 $n \times n$ 的棋盤上放置 $n$ 個皇后，使它們互不攻擊。實現見 n_queens.py，其剪枝依賴列約束與主、副對角線約束；
• 數獨：在 $9 \times 9$ 網格中填入數字 $1 \sim 9$，使每行、每列和每個 $3 \times 3$ 子網格數字不重複；
• 圖著色問題：給定無向圖，用最少的顏色給每個頂點著色，使相鄰頂點顏色不同。

組合最佳化問題——目標是在組合空間中找到滿足某些條件的最優解：

• 0-1 背包問題：給定一組物品和一個背包，每個物品有價值和重量，要求在容量限制內使總價值最大；
• 旅行商問題：在圖中從一個點出發，訪問所有其他點恰好一次後返回起點，求最短路徑；
• 最大團問題：給定無向圖，找到最大的完全子圖。

需要特別強調的是，對許多組合最佳化問題，回溯並非最優解法：

• 0-1 背包問題通常使用動態規劃解決，時間效率更高；
• 旅行商是著名的 NP-Hard 問題，常用解法有遺傳演算法、蟻群演算法等；
• 最大團問題是圖論經典問題，可用貪婪演算法等啟發式演算法解決。

總結

本文以二元樹前序走訪為載體，完整梳理了回溯演算法的知識閉環：解空間的深度優先搜尋 → 嘗試與回退的成對操作 → 基於約束條件的剪枝 → 五鉤子函式的通用框架 → 術語體系 → 適用範圍與效率權衡。從《Hello 算法》的完整範例（Python 見 zh-hant/codes/python/chapter_backtracking，C++ 見 zh-hant/codes/cpp/chapter_backtracking）可以看出，回溯模板的適配成本極低——只需實現is_solution、record_solution、is_valid、make_choice、undo_choice五個函式，即可覆蓋全排列、子集和、N 皇后等一類問題。若想進一步驗證理解，可以繼續閱讀 全排列問題、子集和問題 與 N 皇后問題，並用 練習題 鞏固，最後以 小結 回顧「回溯是演算法策略、遞迴是工具」的關係本質。

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo