跳至主要内容

Backtracking

預備知識

回溯法（Backtracking）是一種窮舉搜尋（Exhaustive Search）的策略，通常配合「剪枝」技術來提早放棄錯誤的路。

白話理解

像是在走迷宮。當走到一個分叉路口，先選一條路往前走；如果走到死路，則退回上一個路口，改走另一條路，直到把所有可能的出路都試完為止。

核心思維：選擇 → 遞迴 → 撤銷​

幾乎所有的 Backtracking 題目，程式碼結構都長得很像，可以歸納成三個步驟：

  1. 做選擇（Choose）：從目前的選項中，挑一個放進目前正在建構的答案裡。
  2. 往下走（Explore）：呼叫遞迴，繼續往下一步做選擇。
  3. 撤銷選擇（Un-choose / Backtrack）：遞迴回來之後，把剛剛的選擇「還原」，讓下一輪迴圈可以嘗試別的選項。
function backtrack(路徑) {
  if (符合結束條件) {
    記錄這個路徑
    return
  }

  for (每一個可能的選擇) {
    做這個選擇        // 1. Choose
    backtrack(路徑)  // 2. Explore
    撤銷這個選擇      // 3. Un-choose，這一步最容易被新手忘記！
  }
}
新手小提醒

第 3 步「撤銷選擇」是新手最容易漏掉的地方。
因為 Backtracking 通常會共用「同一份」路徑資料（例如同一個 array）來節省空間，如果做完選擇、往下遞迴之後不撤銷，這個選擇就會一路殘留下去，汙染到後面其他分支的結果。

範例​

直接以 Leetcode 題目作為範例說明。

題目：列舉 nums 數字的所有排列組合，nums 中沒有重複的數字

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
def permute(nums):
    n = len(nums)
    result = []
    curr = []
    seen = set()

    def helper():
        if len(curr) == n:
            result.append(curr[:])
            return
        for i in range(n):
            if nums[i] in seen:  # 已經放進備選名單，所以跳過
                continue

            curr.append(nums[i])       # 1. Choose：做這個選擇
            seen.add(nums[i])
            helper()                   # 2. Explore：繼續往下遞迴
            curr.pop()                 # 3. Un-choose：撤銷選擇，讓下一輪迴圈可以試別的數字
            seen.remove(nums[i])

    helper()
    return result

逐步拆解：以 nums = [1, 2] 為例​

用比較小的輸入（只有兩個數字）來畫出完整的決策樹，可以更清楚看到「選擇 → 遞迴 → 撤銷」的過程：

                        helper() 第一層
                       curr = []
                      /              \
            選 1 (curr=[1])       選 2 (curr=[2])
                |                       |
        helper() 第二層           helper() 第二層
           curr = [1]                curr = [2]
              |                          |
        選 2 (curr=[1,2])          選 1 (curr=[2,1])
              |                          |
      curr.length === n           curr.length === n
      記錄 [1, 2]                 記錄 [2, 1]
              |                          |
      撤銷成 curr=[1]              撤銷成 curr=[2]
              |                          |
      撤銷成 curr=[]                撤銷成 curr=[]

可以看到，走到 [1, 2] 這個結果之後，程式並不會就此打住，而是把 2 撤銷掉、把 1 也撤銷掉，退回最一開始的空陣列，才能繼續嘗試「先選 2」的另一條路。這個「撤銷」的動作，就是 Backtracking 名稱的由來。

  • Time Complexity: O(n!)
    • 回想中學數學的排列組合，第一個位置有 n 種選擇，第二個位置有 n-1 種選擇...，因此相乘之後是 n!
  • Space Complexity: O(n!)，若不包含輸出內容則為 O(n)

適用情況​

當題目出現以下關鍵字時，通常可以考慮用 Backtracking：

  • 列舉所有可能：排列組合（Permutations）、子集合（Subsets）、組合（Combinations）。
  • 找出所有合法解：例如 N-Queens（皇后問題）、數獨（Sudoku）——每一步都要做選擇，若發現不合法就退回上一步換一種選擇。
  • 路徑搜尋類問題：走迷宮、島嶼數量、單字搜尋（Word Search）——在 Grid 上一步步嘗試，走不通就退回。

常見誤區​

  • 忘記撤銷選擇：如前面提到的，做完選擇、遞迴回來後一定要復原狀態（pop()、delete() 等），否則後續分支會拿到錯誤的路徑。
  • 忘記剪枝，導致明明條件已經不合法還繼續往下走：例如題目要求數字加總不能超過某個值，一旦超過就該直接 return，不需要浪費時間繼續往下遞迴。
  • 和 DFS 搞混：Backtracking 本質上是 DFS 的一種應用（也是用遞迴或 Stack 深入探索），差別在於 Backtracking 特別強調「做錯了會撤銷、換下一個選擇」，通常用來窮舉所有解，而不只是單純走訪一遍。
最後於 更新