回溯演算法原理#

回溯法（Backtracking）本質上是一種帶有**剪枝（Pruning）**功能的深度優先搜尋（DFS）。

核心概念#

回溯法的精髓：嘗試 → 檢查 → 遞迴 → 失敗則撤銷

當發現當前選擇無法得到有效解時，「回溯」到上一步嘗試其他選擇。

回溯程式碼模板#

flowchart TD
    A[開始] --> B{滿足結束條件?}
    B -->|是| C[記錄結果並返回]
    B -->|否| D[遍歷所有選擇]
    D --> E{選擇有效?}
    E -->|否| F[跳過 - 剪枝]
    E -->|是| G[做選擇<br/>path.append]
    G --> H[遞迴<br/>backtrack]
    H --> I[撤銷選擇<br/>path.pop]
    I --> D
    F --> D

    style G fill:#e8f5e9
    style H fill:#e3f2fd
    style I fill:#ffebee
def backtrack(path, choices):
    # 終止條件
    if 滿足結束條件:
        result.append(path[:])  # 記錄結果
        return

    for choice in choices:
        # 剪枝：跳過無效選擇
        if not isValid(choice):
            continue

        # 做選擇
        path.append(choice)

        # 遞迴
        backtrack(path, updated_choices)

        # 撤銷選擇（回溯）
        path.pop()

「撤銷選擇」是回溯法最關鍵的一步！ 若忘記恢復狀態，會導致後續搜尋誤判，遺漏正確解答。

經典案例：括號生成（LeetCode 22）#

給定 n，生成所有合法的 n 對括號組合。

解題思路#

  • 總長度：2n 個字元
  • 每個位置：選擇 ( 或 )
  • 剪枝規則：
    1. 左括號沒用完，隨時可加
    2. 右括號數量不能超過已用的左括號數量

程式碼實作#

def generateParenthesis(n):
    result = []

    def backtrack(left, right, path):
        # 終止條件：左右括號都用完
        if left == n and right == n:
            result.append(path)
            return

        # 選擇 1：加左括號（只要還有剩）
        if left < n:
            backtrack(left + 1, right, path + "(")

        # 選擇 2：加右括號（已用左括號 > 已用右括號）
        if right < left:
            backtrack(left, right + 1, path + ")")

    backtrack(0, 0, "")
    return result

複雜度分析#

  • 時間複雜度：O(4^n / sqrt(n))，與卡特蘭數相關
  • 空間複雜度：O(n)，遞迴深度

回溯 vs 暴力搜尋#

特性暴力搜尋回溯法
搜尋策略窮舉所有組合剪枝排除無效分支
時間複雜度O(2^2n)O(4^n / sqrt(n))
實用性僅適用小規模可處理中等規模

回溯法的效率取決於剪枝的力度。剪枝越精準，搜尋空間越小，效率越高。

回溯適用場景#

  • 排列問題：全排列、字串排列
  • 組合問題：子集、組合總和
  • 搜尋問題：N 皇后、數獨、迷宮
  • 路徑問題：所有可能的路徑
Backward 回溯演算法 剪枝技術 Forward