回溯演算法原理#

回溯法（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
val result = mutableListOf<List<Int>>()

fun backtrack(path: MutableList<Int>, choices: List<Int>) {
    // 終止條件
    if (滿足結束條件) {
        result.add(ArrayList(path))  // 複製一份路徑存起來（不能直接存 path 本身）
        return
    }

    for (choice in choices) {
        // 剪枝：跳過無效選擇
        if (!isValid(choice)) continue

        // 做選擇
        path.add(choice)

        // 遞迴
        backtrack(path, updatedChoices)

        // 撤銷選擇（回溯）
        path.removeAt(path.size - 1)
    }
}

result.add(ArrayList(path)) 一定要複製一份。若直接 result.add(path)，存進去的只是同一個 MutableList 的參照，後續的 add / removeAt 會把已記錄的結果一起改掉。

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

經典案例：括號生成 ↗#

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

解題思路#

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

程式碼實作#

fun generateParenthesis(n: Int): List<String> {
    val result = mutableListOf<String>()

    fun backtrack(left: Int, right: Int, path: String) {
        // 終止條件：左右括號都用完
        if (left == n && right == n) {
            result.add(path)  // path 是 String（不可變），直接存即可，無須複製
            return
        }

        // 加左括號（只要還有剩）
        if (left < n) {
            backtrack(left + 1, right, "$path(")
        }

        // 加右括號（已用左括號 > 已用右括號）
        if (right < left) {
            backtrack(left, right + 1, "$path)")
        }
    }

    backtrack(0, 0, "")
    return result
}

複雜度分析#

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

回溯 vs 暴力搜尋#

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

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

回溯適用場景#

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