---
title: "797. All Paths From Source to Target"
url: "https://laigary.com/interview/coding/797-all-paths-from-source-to-target"
type: "note"
section: "coding"
date: "2024-02-22"
updated: "2026-08-02"
tags: ["Graph", "Backtrack", "Depth-First Search"]
---

# 797. All Paths From Source to Target

[797\. All Paths From Source to Target](https://leetcode.com/problems/all-paths-from-source-to-target/)

給一張有向無環圖（DAG）的鄰接表，`graph[i]` 是節點 `i` 可以走到的所有節點。求從節點 `0` 到節點 `n - 1` 的**所有**路徑。

## 思路

### 要「所有」就是回溯法

題目要的不是「到得了嗎」也不是「最短幾步」，而是把每一條路徑都列出來 —— 這就是[回溯法](/interview/coding/backtracking-template)：做選擇、遞迴、撤銷選擇。

骨架完全是模板：站在節點 `i`，`graph[i]` 就是這一層的選項，走到 `n - 1` 就收下一條答案。

### 模板沒有規定的那件事

模板規定了「做選擇 → 遞迴 → 撤銷選擇」，但它**沒有規定「一個節點是在哪一刻被算進路徑的」**。這題會特別容易分岔，是因為**起點也是答案的一部分**：節點 `0` 從來沒有被任何一層「選擇」過，它一開始就在那裡了。

於是就有兩種都說得通的處理法：要嘛每個節點自己把自己放進路徑，要嘛由上一層在迴圈裡幫它放、而起點在最外面先放好。

### 兩種約定

要問自己的只有一句話：**「進到函式的那一刻，`curr` 裡面有沒有包含我現在站的這個點？」**

這個答案決定了整個函式的每一行：

| | 約定 A：自己加自己 | 約定 B：幫小孩加 |
|---|---|---|
| 進函式時 `curr` 含不含 `i` | **不含** | **含** |
| 誰負責 `append` | 函式自己，第一行 | 呼叫我的那一層，在迴圈裡 |
| 起點怎麼呼叫 | `backtrack([], 0)` | `backtrack(0, [0])`，起點要先放好 |
| base case 寫在哪 | 一定要在 `append` **之後** | 可以在第一行，直接讀 `curr[-1]` |
| `pop` 在哪 | 函式最後一行，只有一個 | 迴圈裡，跟 `append` 貼在一起 |

### 混起來會少一個點

兩種各自都對，混起來就會出事，而且錯得很安靜：

```python
def backtrack(curr, i):
    if i == len(graph) - 1:      # ← B 的位置：在 append 之前就判斷
        res.append(list(curr))   #   但這裡 curr 還沒有 i
        return
    curr.append(i)               # ← A 的做法：自己加自己
    for path in graph[i]:
        backtrack(curr, path)
    curr.pop()

backtrack([], 0)                 # ← A 的呼叫方式：起點沒有先放進去
```

終點永遠進不了答案：

```text
graph = [[1,2],[3],[3],[]]
  輸出   [[0, 1], [0, 2]]
  正解   [[0, 1, 3], [0, 2, 3]]
```

## 解題方向

四種寫法都是對的（各跑 4000 個隨機 DAG 對過暴力枚舉），差別只在上面那個約定，以及 `append` 出現幾次。

### 寫法一：約定 A，但 base case 裡又補了一次

```python
class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        
        dest = len(graph) - 1
        res = []
        
        def backtrack(curr, i):
            if i == dest:
                curr.append(i)
                res.append(curr.copy())
                curr.pop()
                return
            
            curr.append(i)
            for node in graph[i]:
                backtrack(curr, node)    
            curr.pop()
            
        backtrack([], 0)
        
        return res
            
```

`curr.append(i)` 出現了**兩次** —— 一次在 base case 裡（配一次 `pop` 和 `return`），一次在下面。它是對的，但這也是四種裡唯一「同一件事要記得寫兩遍」的版本，漏掉 base case 那次就會變成上面那個少一個點的 bug。

### 寫法二：約定 B，另外帶 visited

```python
class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        target = len(graph) - 1
        res = []
        
        def backtrack(i, curr, visited):
            if len(curr) > 0 and curr[-1] == target:
                res.append(curr.copy())
                return
            
            for node in graph[i]:
                if node not in visited:
                    curr.append(node)
                    visited.add(node)
                    backtrack(node, curr, visited)
                    visited.remove(node)
                    curr.pop()
            
        
        backtrack(0, [0], set([0]))
        return res
```

起點在呼叫時就放好了（`backtrack(0, [0])`），所以 base case 可以直接讀 `curr[-1]`，`append` / `pop` 成對包在迴圈裡。

這一版有兩個東西是不需要的：

- **`visited` 在這題是死碼。** 題目保證是 DAG，同一條路上不可能再遇到自己。實測 4000 個隨機 DAG、21062 次呼叫，`if node not in visited` **一次都沒有擋掉東西**。
- **`len(curr) > 0` 永遠成立。** `curr` 從 `[0]` 開始，之後只會在迴圈裡先 `append` 再遞迴，同一組 instrument 跑下來 `curr` 從來沒有空過。

### 寫法三：約定 B

```python
class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        target = len(graph) - 1
        res = []
        
        def backtrack(i, curr):
            if len(curr) > 0 and curr[-1] == target:
                res.append(curr.copy())
                return
            
            for node in graph[i]:
                curr.append(node)
                backtrack(node, curr)
                curr.pop()
            
        
        backtrack(0, [0])
        return res
```

寫法二拿掉 `visited` 就是這一版，也是四種裡最短的。

### 寫法四：約定 A，append 只出現一次

```python
class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        
        res = []

        def backtrack(curr, i):
            curr.append(i)
            if i == len(graph) - 1:
                res.append(list(curr))
            else:
                for path in graph[i]:
                    backtrack(curr, path)
            curr.pop()
        

        backtrack([], 0)

        return res
```

`append` 是第一行、`pop` 是最後一行、中間用 `else` 接住 base case **所以不 return** —— 三件事一守住，就沒有地方可以漏。四種裡最不容易寫錯的是這一版。

## 補充

### 有模板了，為什麼還會寫出四種？

因為模板是**骨架**不是**不變式**。「做選擇 → 遞迴 → 撤銷選擇」只說了順序，沒說「選擇」這個動作發生在呼叫的哪一邊。

Subsets、Combination Sum 那類題目不會有這個困擾，是因為路徑從**空的**開始長，每一個元素都是被某一層迴圈選進來的，只有約定 B 一種寫法。而這題的起點 `0` 是白吃的 —— 它在答案裡，卻沒有被任何一層選過。**凡是「起點本身就算答案的一部分」的圖論題，都會分岔成這兩種寫法。**

### 怎麼收斂

三個檢查，寫之前先做完：

1.  **先用一句話寫下不變式，再開始寫程式。** 「進到 `backtrack(i, curr)` 時，`curr` 已經是 `[0..i]`（含 `i`）」或者「不含 `i`」—— 二選一，寫在註解裡也好。剩下的每一行都是它推出來的，不用再憑感覺。
2.  **數 `append` 和 `pop`。** 兩者必須一比一，而且最好只各出現一次。出現兩次就代表有兩條離開這一層的路徑（正常結束 + `return`），漏掉任何一邊就會壞。
3.  **看 base case 讀的是什麼。** 讀 `curr[-1]` → 必須是約定 B；讀參數 `i` → 必須先確定 `i` 已經進 `curr` 了。**這次寫錯就是踩在這一條上。**

面試時建議固定用寫法四那個形狀：`append` 第一行、`pop` 最後一行、base case 用 `else` 而不是 `return`。形狀固定了，就不用每次重新想一遍。

## 複雜度

四種寫法的複雜度完全相同。設 $n$ 是節點數。

- 時間 $O(2^n \times n)$ — 最壞情況是「所有 `i < j` 都有邊」的完全 DAG，中間 `n - 2` 個節點各自可走可不走，路徑數就是 $2^{n-2}$（實測 `n` 從 3 到 8 分別是 2、4、8、16、32、64 條）；每收下一條路徑還要 $O(n)$ 複製進 `res`
- 空間 $O(n)$ — `curr` 最長是 `n`，遞迴深度也是 `n`；寫法二多帶的 `visited` 一樣是 $O(n)$。回傳的 `res` 不計入