Learning Objectives
- 說出回溯法「做選擇、遞迴、撤銷選擇」的三個步驟，並在程式裡找出它們
- 把排列與子集合的產生過程畫成決策樹，追蹤路徑在每一步怎麼變化
- 用回溯法解 N 皇后問題，說明行與斜線的衝突怎麼檢查
- 用剪枝提早放棄不可能成功的分支，說明剪枝成立的前提
- 估計回溯法的時間複雜度，知道它在最壞情況下仍是指數時間
把所有可能一個一個試出來
排座位、排值日生、從一堆零錢裡湊出剛好 100 元、在棋盤上擺棋子不互相攻擊：這些問題都沒有一條公式能直接算出答案， 但它們有一個共同點：答案是一連串的選擇。第一個位置坐誰、第二個位置坐誰……每一步都有幾個選項，選完所有步驟就得到一個候選答案。
回溯法（backtracking）就是有系統地試遍這些選擇：
- 做選擇：從目前可以選的選項裡挑一個，記到「路徑」上
- 遞迴：帶著這個選擇，去決定下一步
- 撤銷選擇：從下一步回來以後，把剛才的選擇拿掉，換下一個選項再試
第 3 步就是「回溯」這個名字的由來：走進死路，就退回上一個岔路口換一條路。 把所有選擇畫成一棵樹，回溯法其實就是在這棵決策樹上做深度優先搜尋（DFS，第 17 課），一路走到底再退回來。
def backtrack(路徑, 選項):
if 路徑已經完整:
記錄答案
return
for 選項 in 目前可以選的:
做選擇
backtrack(新的路徑, 新的選項)
撤銷選擇
這一課用這個模板解四個問題：排列、子集合、N 皇后，以及用剪枝加速的子集和。
排列：每一層決定一個位置
把 1、2、3 排成所有可能的順序。遞迴樹的每一層決定一個位置：第一層選第一個數，第二層選第二個數。注意 path 在整個過程中只有一個：往下走時 append，回來時 pop，所以它永遠是「從根走到目前節點」的那條路。6 片葉子對應 6 個排列，也就是 3! = 6。
撤銷選擇為什麼不能省
path 和 used 是所有遞迴呼叫共用的同一份資料（範例把它們放在函式外面，每一層讀寫的都是它們）。
如果從下一層回來時不把選擇撤銷，上一層的迴圈換下一個數字時，路徑上還留著剛才那個數字，後面產生的結果就全錯了。
撤銷的順序要和做選擇的順序相反：先 used[i] = True 再 append，回來時就先 pop 再 used[i] = False。這樣每一層回到迴圈開頭時，狀態都和進入這一層時一模一樣。
有多少個節點？ n 個不同的數字有 n! 個排列，決策樹的葉子就有 n! 片，每片葉子印出一個長度 n 的結果，所以時間是 O(n × n!)。
| n | n! |
|---|---|
| 3 | 6 |
| 5 | 120 |
| 8 | 40,320 |
| 10 | 3,628,800 |
| 12 | 479,001,600 |
回溯法能保證不漏掉任何答案，代價是答案本身就有這麼多個。第 25 課會看到這種成長速度為什麼讓某些問題「難解」。
子集合：每個節點都是一個答案
子集合和排列不同：{1, 2} 和 {2, 1} 是同一個子集合，所以選了 nums[i] 以後，下一層只能從 i + 1 開始選，不能回頭選前面的數。另一個差別是每個節點都是答案（不必等到路徑滿了），所以進入函式就先印出目前的路徑。3 個數字有 2³ = 8 個子集合，遞迴樹剛好有 8 個節點。
想一想：排列與子集合
用上面的子集合程式處理 nums = [1, 2, 3]，印出的第 5 行是什麼？
排列程式少寫了 path.pop()（used[i] = False 還在），用 nums = [1, 2] 執行，會印出什麼？
5 個不同的數字，排列程式的決策樹有幾片葉子（印出幾行）？子集合程式印出幾行？
N 皇后：在棋盤上放互不攻擊的皇后
西洋棋的皇后可以沿著同一列、同一行、兩條斜線走任意格。N 皇后問題：在 N × N 的棋盤上放 N 個皇后，讓任兩個都不在同一列、同一行或同一條斜線上。
直接列舉「N² 格裡選 N 格」太多了（8 × 8 棋盤選 8 格超過 44 億種）。回溯法的做法是利用規則縮小選項：
- 每一列剛好放一個皇后，所以一列一列放：第
row層只決定第row列的皇后放在哪一行 - 放之前先檢查這一格有沒有被前面的皇后攻擊到，有的話直接跳過，不往下走
檢查衝突用三個布林陣列，每次查詢都是 O(1)：
| 陣列 | 意思 | 索引 |
|---|---|---|
cols |
這一行有沒有皇后 | col |
d1 |
左上到右下的斜線：同一條線上 row + col 都相同 |
row + col（0～2N-2） |
d2 |
右上到左下的斜線：同一條線上 row - col 都相同 |
row - col + N - 1（加 N-1 讓索引不是負數） |
下面的範例找出 4 皇后的第一組解就停下來：solve(row) 回傳「從第 row 列往下能不能全部放好」，下一層成功就一路回傳成功，不再試別的位置。
4 皇后：放不下就退回上一列
第 0 列先把皇后放在第 0 行，結果第 1 列試了兩個位置、往下都走不通，最後整條路失敗，退回第 0 列改放第 1 行。看遞迴樹：回傳 F 的節點就是死路，回傳 T 的是成功的那一條。4 皇后共有 2 組解（左右鏡像），這個範例找到第一組就停。
更大的棋盤有幾組解
把範例改成「找到一組解不停下來，而是數一數」，就能算出每個 N 的解數。只看結果（不逐步播放）：
| N | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|
| 解數 | 2 | 10 | 4 | 40 | 92 |
N = 2、3 沒有解；N = 6 的解反而比 N = 5 少。8 皇后的 92 組解裡，扣掉旋轉與鏡像後是 12 組本質不同的解。
這一課最後的實作就是把這個數解的程式寫出來。
剪枝：提早放棄不可能成功的分支
N 皇后裡「這一格被攻擊就跳過」已經是一種剪枝（pruning）：不用把皇后放下去、往下走到最後一列，才發現失敗。 剪掉一個節點，它底下的整棵子樹都不用走了，這是回溯法比單純列舉快的關鍵。
子集和問題：從 [2, 3, 5, 6, 8] 裡挑一些數，讓總和剛好是 10。不剪枝的話，要走過全部 2⁵ = 32 個子集合。
如果數字已經由小到大排好，可以加一條規則：
目前的總和加上
nums[i]已經超過 10，就不用試nums[i]；而且後面的數更大，也都不用試，直接break。
這條規則成立的前提是「排好序」而且「數字都是正的」。如果有負數，現在超過了，之後加上負數還可能拉回來，就不能這樣剪。 剪枝一定要確定被剪掉的分支不可能有答案，否則會漏掉解。
子集和：超過目標就不再往下
看遞迴樹節點上的總和：沒有一個超過 10。例如總和是 5（選了 2、3）時，下一個數 6 會讓總和變成 11，程式在這裡 break，8 也不試了。最後只呼叫了 13 次，不剪枝要 32 次。
想一想：N 皇后與剪枝
4 皇后的範例裡，row = 1, col = 0 這一格為什麼一檢查就跳過？（第 0 列的皇后在第 0 行）
子集和的範例裡，如果 nums 沒有排序（例如 [2, 9, 3, 5]），total + nums[i] > target 時還能直接 break 嗎？
下面哪一個敘述正確？
實作：數出 N 皇后的解數
完成 count：它回傳「從第 row 列放到最後一列，共有幾種放法」。和範例不同的是，找到一組解以後不要停，要把每一格往下數到的解數加起來。程式會印出 N = 4～8 的解數。
重點整理
- 回溯法＝做選擇、遞迴、撤銷選擇；它是在決策樹上做深度優先搜尋
- 共用的狀態（路徑、已使用標記）從下一層回來時一定要撤銷，順序和做選擇時相反
- 排列：每一層決定一個位置，用
used避免重複使用，共 n! 個 - 子集合：下一層從
i + 1開始選，每個節點都是答案，共 2ⁿ 個 - N 皇后：一列放一個，用
cols、d1（row + col）、d2（row - col + n - 1）在 O(1) 內檢查衝突 - 剪枝：確定不可能有答案的分支就不走；剪枝的條件必須真的成立（例如排序後才能
break） - 剪枝讓實際執行快很多，但最壞情況通常仍是指數時間
下一課：字串比對。在一長段文字裡找出某個字串出現的位置，看 KMP 怎麼利用已經比對過的資訊，避免從頭再比。