Backtracking 模板
Backtracking 的本質是「窮舉一棵決策樹」，模板永遠是同一套：
- 做選擇 — 把當前選項加進路徑
- 遞迴 — 帶著新狀態往下走
- 撤銷選擇 — 回到上一步，換下一個選項
def backtrack(路徑, 選項):
if 滿足結束條件:
結果.append(路徑[:]) # 注意要複製
return
for 選 in 選項:
路徑.append(選) # 做選擇
backtrack(路徑, 新的選項)
路徑.pop() # 撤銷選擇
模板是骨架，填空的內容由下面四個問題決定。
讀題時的四個問題
| 問題 | 決定了什麼 | |
|---|---|---|
| 一 | 候選集合怎麼縮？ | 傳 i + 1 / 傳 i / 用 used、visited |
| 二 | 候選有幾個？ | 要不要 for 迴圈 |
| 三 | 什麼時候收答案？ | base case 放哪、收完要不要 return |
| 四 | 有沒有東西可以剪？ | break / continue 的位置 |
四個都是題目決定的，讀完題就該有答案。至於「路徑什麼時候 append」則是你自己的約定，見最後一節。
一、候選集合怎麼縮
三種手段，其實在回答同一句話：下一層還能選什麼。
往後縮（Subsets 型）：用 start
每個節點都是答案，用 start 避免回頭產生重複組合。
def backtrack(start, path):
res.append(path[:]) # 每個節點都收
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i + 1, path) # i + 1：不回頭
path.pop()
例題：78. Subsets、77. Combinations
不縮（Combination Sum 型）：可以重複選自己
跟 Subsets 唯一的差別是遞迴時傳 i 而不是 i + 1。
backtrack(i, path) # i：同一個元素可以再選
挖洞（Permutations 型）：用 used 記錄「誰被選過」
順序有意義，所以每層都從頭掃，用 used 排除已在路徑上的元素。
def backtrack(path):
if len(path) == len(nums):
res.append(path[:])
return
for i in range(len(nums)):
if used[i]:
continue
used[i] = True
path.append(nums[i])
backtrack(path)
path.pop()
used[i] = False
挖洞的三個名字是同一件事
used 陣列、圖題的 visited、51. & 52. N Queens 的 cols / diagonals / anti_diagonals —— 全部都在記同一件事：這個資源在我這條路徑上已經被佔走了。N Queens 只是同時記三種資源而已（46 的實作用的也是 visited 而不是 used，名字不重要）。
所以判準不是「要不要 visited」，而是 index 夠不夠用：
- 能用
i + 1往後縮 → 不需要，i + 1已經隱含「前面的不能再選」 - 不能（排列要回頭選、圖上沒有線性順序）→ 才需要挖洞
圖上還要再多問一句有沒有環：797. All Paths From Source to Target 保證是 DAG，同一條路上不可能再遇到自己，所以連 visited 都不用。
二、候選有幾個 —— 固定兩個就不用迴圈
for 迴圈是用來走候選集合的。候選固定只有兩個，迴圈就退化成兩段遞迴：
def backtrack(curr = [], left = 0, right = 0):
if left == n and right == n:
ans.append(''.join(curr))
return
if left < n: # left can not exceeds n
curr.append('(')
backtrack(curr, left + 1, right)
curr.pop()
if right < left: # right can not exceeds left
curr.append(')')
backtrack(curr, left, right + 1)
curr.pop()
樹的題目是同一型（候選永遠是 left / right）：113. Path Sum II、257. Binary Tree Paths。
78. Subsets 是最好的示範題 —— 它兩種都能寫：「選 / 不選」的兩段遞迴，或上面那種從 start 挑一個的迴圈。同一棵決策樹的兩種切法。
三、什麼時候收答案
這決定 base case 放哪、以及收完要不要 return：
| 收答案的時機 | base case 長相 | 例題 |
|---|---|---|
| 走到底才收 | if len(path) == n / if row == n，收完 return | 46、51 |
| 滿足條件才收 | if rem == 0，收完 return | 39、40 |
| 每個節點都是答案 | res.append(path[:]) 放在函式開頭，而且不能 return | 78、90 |
| 走到葉節點才收 | if not node.left and not node.right | 113、257 |
第三列最會咬人：78 的每個節點本身就是一個子集合，照抄「收完就 return」的手勢，後面的子集合全部生不出來。
四、剪枝
在 for 迴圈裡提前 break / continue 掉不可能的分支，是唯一能救時間複雜度的手段：
- 剩餘的和已經超過 target →
break（排序後可以直接斷整層） - 剩下的元素不夠湊滿 k 個 → 縮小
range上界 - 位置不合法（如 N Queens 的斜線衝突）→
continue
例題：22. Generate Parentheses、131. Palindrome Partitioning、79. Word Search、51. & 52. N Queens
去重：要的不是排序，是「固定的順序」
輸入有重複元素時，先排序，然後同一層遇到跟前一個一樣的元素直接跳過（前一個沒被用，代表這是同層的重複分支）：
nums.sort()
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i - 1]: # 同層去重
continue
例題：90. Subsets II、40. Combination Sum II
排序本身不是目的 —— 真正需要的是讓相同的值之間有一個固定的先後順序，這樣每個組合只會以一種順序被產生。排序是最省事的取得方式，順便還送你 break 剪枝。
兩個推論值得記住：
- 不排序的話，光靠「同層 seen set」是不夠的。
[1, 2, 1]、target 3 會生出兩次[1, 2]—— 選了 index 1 的2之後，後面還有一個1可以撿。排序之後不可能發生，因為往後走只會遇到更大的值。 - 改對「相異值」做選擇就完全不用排序（用
Counter決定每種值拿幾個），因為相異值的列表本身就是那個固定順序。
排序的 不會影響複雜度 —— 搜尋本身是指數等級，排序被整個吃掉。
path 的 append / pop 是你的約定，不是題目的
上面四個問題都由題目決定，這一個不是 —— 同一題兩種寫法都對，混用才會出事：
| 約定 A：自己加自己 | 約定 B：幫小孩加 | |
|---|---|---|
| 進函式時 path 含不含當前這個點 | 不含 | 含 |
誰 append | 函式自己，第一行 | 上一層，在迴圈裡 |
| 起點怎麼呼叫 | backtrack([], 0) | backtrack(0, [0])，起點先放好 |
| base case | 必須在 append 之後 | 可以在第一行，直接讀 path[-1] |
pop | 函式最後一行，只有一個 | 迴圈裡，跟 append 貼著 |
固定用一種，不要每題重想。 建議是約定 A 的形狀：append 第一行、pop 最後一行、base case 用 else 接住所以不 return —— append / pop 各只出現一次，沒有地方可以漏。
踩過的坑見 797. All Paths From Source to Target：用 A 的呼叫方式配 B 的 base case 位置，答案會固定少掉最後一個點。
面試時的講法
先講「這是窮舉問題，我用 backtracking」，畫出決策樹的前兩層，然後把上面四個問題講一遍：候選怎麼縮（start / used / visited）、候選有幾個（要不要迴圈）、哪裡收答案（葉子還是每個節點）、哪裡可以剪枝。講完這四點再動手，code 幾乎是照模板填空。
更多題目 → #Backtrack