LeetCode 797: All Paths From Source to Target

Problem Restatement

We are given a directed acyclic graph, also called a DAG.

The graph has n nodes labeled:

0, 1, 2, ..., n - 1

The graph is represented as an adjacency list. graph[i] contains every node we can visit directly from node i.

We need to return all possible paths from node 0 to node n - 1, in any order. The graph is guaranteed to be directed and acyclic.

Input and Output

Function shape:

class Solution:
    def allPathsSourceTarget(self, graph: list[list[int]]) -> list[list[int]]:
        ...

Examples

Example 1:

graph = [[1, 2], [3], [3], []]

The graph has these edges:

0 -> 1
0 -> 2
1 -> 3
2 -> 3

All paths from 0 to 3 are:

[
    [0, 1, 3],
    [0, 2, 3],
]

Example 2:

graph = [[4, 3, 1], [3, 2, 4], [3], [4], []]

The target is node 4.

Valid paths include:

[0, 4]
[0, 3, 4]
[0, 1, 3, 4]
[0, 1, 2, 3, 4]
[0, 1, 4]

So the result is:

[
    [0, 4],
    [0, 3, 4],
    [0, 1, 3, 4],
    [0, 1, 2, 3, 4],
    [0, 1, 4],
]

First Thought: Explore Every Route

The problem asks for all paths, not just one path or the shortest path.

So we must explore every possible route from the source to the target.

This naturally suggests depth-first search.

During DFS, we keep a current path.

When we reach the target node, we copy the current path into the answer.

Then we backtrack and try another neighbor.

Key Insight

Because the graph is acyclic, DFS will not get stuck in an infinite loop.

At each node:

1. Add the node to the current path.
2. Explore every outgoing neighbor.
3. If the target is reached, save the path.
4. Remove the node when returning to the previous call.

This is standard backtracking.

The path changes as recursion goes deeper, and backtracking restores it so other branches can reuse the same list.

Algorithm

1. Let target = len(graph) - 1.
2. Create an empty list answer.
3. Start DFS from node 0 with path [0].
4. In DFS:
   1. If the current node is target, append a copy of the path.
   2. Otherwise, for each neighbor:
      1. Append the neighbor to the path.
      2. Recurse from that neighbor.
      3. Pop the neighbor from the path.
5. Return answer.

Correctness

The DFS starts at node 0, so every path it builds begins at the source.

Whenever DFS moves from a node to a neighbor, that neighbor appears in the current node’s adjacency list. Therefore, every step in the path follows a valid directed edge.

When DFS reaches node n - 1, it saves the current path. Since the path starts at 0, ends at n - 1, and follows only graph edges, every saved path is valid.

Now consider any valid path from 0 to n - 1. At each node on that path, the next node is one of the outgoing neighbors. DFS tries every outgoing neighbor from every visited node, so it will choose the same sequence of nodes at some point. Therefore, DFS will eventually generate and save that valid path.

Thus, the algorithm returns exactly all valid paths from source to target.

Complexity

Let P be the number of valid paths, and let n be the number of nodes.

The recursion stack and current path use O(n) extra space.

The output itself can be exponential because a DAG may contain exponentially many source-to-target paths.

Implementation

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

        def dfs(node: int) -> None:
            if node == target:
                answer.append(path.copy())
                return

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

        dfs(0)
        return answer

Code Explanation

The target node is the last node:

target = len(graph) - 1

We store all complete paths here:

answer = []

The current path starts at source node 0:

path = [0]

When DFS reaches the target, we save a copy:

if node == target:
    answer.append(path.copy())
    return

The copy is important. If we append path directly, later pop() operations would mutate the saved result.

For each outgoing edge, we extend the path:

path.append(neighbor)
dfs(neighbor)
path.pop()

The pop() restores the path before trying the next neighbor.

BFS Version

We can also store whole paths in a queue.

from collections import deque

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

        while queue:
            path = queue.popleft()
            node = path[-1]

            if node == target:
                answer.append(path)
                continue

            for neighbor in graph[node]:
                queue.append(path + [neighbor])

        return answer

This is easy to read, but it creates many copied path lists during traversal. The DFS version copies only when saving a complete path.

Testing

def normalize(paths):
    return sorted(paths)

def run_tests():
    s = Solution()

    assert normalize(s.allPathsSourceTarget([[1, 2], [3], [3], []])) == normalize([
        [0, 1, 3],
        [0, 2, 3],
    ])

    assert normalize(s.allPathsSourceTarget([[4, 3, 1], [3, 2, 4], [3], [4], []])) == normalize([
        [0, 4],
        [0, 3, 4],
        [0, 1, 3, 4],
        [0, 1, 2, 3, 4],
        [0, 1, 4],
    ])

    assert s.allPathsSourceTarget([[1], []]) == [[0, 1]]

    assert normalize(s.allPathsSourceTarget([[1, 2, 3], [4], [4], [4], []])) == normalize([
        [0, 1, 4],
        [0, 2, 4],
        [0, 3, 4],
    ])

    print("all tests passed")

run_tests()

Test coverage: