797. All Paths From Source to Target

Problem¶

Given a DAG as adjacency lists, return every directed path from node 0 to node n - 1 in any order.

graph = [[1, 2], [3], [3], []]
0 -> 1 -> 3
0 -> 2 -> 3
result = [[0, 1, 3], [0, 2, 3]]

Key trick¶

Use DFS backtracking: keep one current path, append a neighbor before recursion, and remove it afterward. Since the graph is acyclic, no visited set is needed.

Trap¶

• A global visited set incorrectly removes valid paths that converge at the same node.
• Store a copy of the path at the target; otherwise later backtracking mutates the stored result.
• Do not stop after finding the first path.

Why is it interesting?¶

It is a compact example of output-sensitive enumeration and shows when backtracking does not require cycle detection.

Python solution¶

class Solution:
    def allPathsSourceTarget(self, graph: list[list[int]]) -> list[list[int]]:
        target = len(graph) - 1
        res = []
        path = [0]

        def dfs(node):
            if node == target:
                res.append(path[:])
                return

            for nxt in graph[node]:
                path.append(nxt)
                dfs(nxt)
                path.pop()

        dfs(0)
        return res

• Time: \(O(Q + L)\), where \(Q\) is the number of explored path-prefix nodes and \(L\) is the total size of the returned paths; worst case \(O(n2^n)\).
• Auxiliary space: \(O(n)\) excluding the output.
• Output space: \(O(L)\).

Comment on my solution¶

• Your reverse BFS is correct: building predecessor lists lets the search consider only nodes that can lead to the target.
• Duplicate handling is unnecessary because unique edges and the DAG property make each sequence of vertices a distinct path.
• The level-sized loop does not affect the result and can be removed because paths need not be grouped by length.
• path[:] is unnecessary when adding to res, since that path object is never mutated.
• [prev] + path copies the whole partial path at every step, increasing allocation costs; DFS backtracking reuses one list and copies only completed paths.
• Building predecessor lists also uses \(O(n + E)\) additional space, while forward DFS can traverse the provided adjacency lists directly.

# Ideas:
# - reachability problem
# - as we have to enumerate:
#   - maybe dfs backtracking (starting at node 0)
#     - must be careful to not include duplicates in output
#     - would be great to not compute several time suffixes
# - maybe start from the end, the node n - 1 and build path backward
#   - if we reach 0, include the path
#     - this way it seems that paths in output will be unique


from collections import deque

# WORKS
class Solution:
    def allPathsSourceTarget(self, graph: list[list[int]]) -> list[list[int]]:
        n = len(graph)
        predecessors = [[] for _ in range(n)]
        for src in range(n):
            for dst in graph[src]:
                predecessors[dst].append(src)
        res = []
        q = deque([(n - 1, [n - 1])]) # (node, path node to n - 1)
        while q:
            for _ in range(len(q)):
                node, path = q.popleft()
                if node == 0:
                    res.append(path[:])
                    continue
                for prev in predecessors[node]:
                    q.append((prev, [prev] + path))
        return res