797. All Paths From Source to Target

──────────────────────────────────────────────────────────────────────

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

思路

要「所有」就是回溯法

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

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

模板沒有規定的那件事

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

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

兩種約定

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

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

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

混起來會少一個點

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

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 的呼叫方式：起點沒有先放進去

終點永遠進不了答案：

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

解題方向

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

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

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

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

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 只出現一次

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 是白吃的 —— 它在答案裡，卻沒有被任何一層選過。凡是「起點本身就算答案的一部分」的圖論題，都會分岔成這兩種寫法。

怎麼收斂

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

先用一句話寫下不變式，再開始寫程式。 「進到 backtrack(i, curr) 時，curr 已經是 [0..i]（含 i）」或者「不含 i」—— 二選一，寫在註解裡也好。剩下的每一行都是它推出來的，不用再憑感覺。
數 append 和 pop。 兩者必須一比一，而且最好只各出現一次。出現兩次就代表有兩條離開這一層的路徑（正常結束 + return），漏掉任何一邊就會壞。
看 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 不計入