---
title: "Backtracking 模板"
url: "https://laigary.com/interview/coding/backtracking-template"
type: "note"
section: "coding"
date: "2026-07-24"
updated: "2026-08-02"
tags: ["Backtrack"]
---

# Backtracking 模板

Backtracking 的本質是「窮舉一棵決策樹」，模板永遠是同一套：

1. **做選擇** — 把當前選項加進路徑
2. **遞迴** — 帶著新狀態往下走
3. **撤銷選擇** — 回到上一步，換下一個選項

```python
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` 避免回頭產生重複組合。

```python
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](/interview/coding/78-subsets)、[77. Combinations](/interview/coding/77-combinations)

### 不縮（Combination Sum 型）：可以重複選自己

跟 Subsets 唯一的差別是遞迴時傳 `i` 而不是 `i + 1`。

```python
        backtrack(i, path)           # i：同一個元素可以再選
```

例題：[39. Combination Sum](/interview/coding/39-combination-sum)

### 挖洞（Permutations 型）：用 used 記錄「誰被選過」

順序有意義，所以每層都從頭掃，用 `used` 排除已在路徑上的元素。

```python
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
```

例題：[46. Permutations](/interview/coding/46-permutations)

### 挖洞的三個名字是同一件事

`used` 陣列、圖題的 `visited`、[51. & 52. N Queens](/interview/coding/51-52-n-queens) 的 `cols` / `diagonals` / `anti_diagonals` —— 全部都在記同一件事：**這個資源在我這條路徑上已經被佔走了**。N Queens 只是同時記三種資源而已（[46](/interview/coding/46-permutations) 的實作用的也是 `visited` 而不是 `used`，名字不重要）。

所以判準不是「要不要 visited」，而是 **index 夠不夠用**：

- 能用 `i + 1` 往後縮 → 不需要，`i + 1` 已經隱含「前面的不能再選」
- 不能（排列要回頭選、圖上沒有線性順序）→ 才需要挖洞

圖上還要再多問一句**有沒有環**：[797. All Paths From Source to Target](/interview/coding/797-all-paths-from-source-to-target) 保證是 DAG，同一條路上不可能再遇到自己，所以連 `visited` 都不用。

## 二、候選有幾個 —— 固定兩個就不用迴圈

`for` 迴圈是用來走候選集合的。**候選固定只有兩個，迴圈就退化成兩段遞迴**：

```python
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](/interview/coding/113-path-sum-ii)、[257. Binary Tree Paths](/interview/coding/257-binary-tree-paths)。

[78. Subsets](/interview/coding/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](/interview/coding/22-generate-parentheses)、[131. Palindrome Partitioning](/interview/coding/131-palindrome-partitioning)、[79. Word Search](/interview/coding/79-word-search)、[51. & 52. N Queens](/interview/coding/51-52-n-queens)

## 去重：要的不是排序，是「固定的順序」

輸入有重複元素時，先排序，然後**同一層**遇到跟前一個一樣的元素直接跳過（前一個沒被用，代表這是同層的重複分支）：

```python
nums.sort()
for i in range(start, len(nums)):
    if i > start and nums[i] == nums[i - 1]:  # 同層去重
        continue
```

例題：[90. Subsets II](/interview/coding/90-subsets-ii)、[40. Combination Sum II](/interview/coding/40-combination-sum-ii)

排序本身不是目的 —— 真正需要的是**讓相同的值之間有一個固定的先後順序**，這樣每個組合只會以一種順序被產生。排序是最省事的取得方式，順便還送你 `break` 剪枝。

兩個推論值得記住：

- **不排序的話，光靠「同層 seen set」是不夠的。** `[1, 2, 1]`、target 3 會生出兩次 `[1, 2]` —— 選了 index 1 的 `2` 之後，後面還有一個 `1` 可以撿。排序之後不可能發生，因為往後走只會遇到更大的值。
- **改對「相異值」做選擇就完全不用排序**（用 `Counter` 決定每種值拿幾個），因為相異值的列表本身就是那個固定順序。

排序的 $O(n \log n)$ 不會影響複雜度 —— 搜尋本身是指數等級，排序被整個吃掉。

## 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](/interview/coding/797-all-paths-from-source-to-target)：用 A 的呼叫方式配 B 的 base case 位置，答案會固定少掉最後一個點。

## 面試時的講法

先講「這是窮舉問題，我用 backtracking」，畫出決策樹的前兩層，然後把上面四個問題講一遍：**候選怎麼縮**（start / used / visited）、**候選有幾個**（要不要迴圈）、**哪裡收答案**（葉子還是每個節點）、**哪裡可以剪枝**。講完這四點再動手，code 幾乎是照模板填空。

更多題目 → [#Backtrack](/interview/coding?tag=Backtrack)