# 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:

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

| Item | Meaning |
|---|---|
| Input | `graph`, an adjacency list |
| Output | All paths from node `0` to node `n - 1` |
| Source | Node `0` |
| Target | Node `n - 1` |
| Graph type | Directed acyclic graph |
| Output order | Any order is accepted |

Function shape:

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

## Examples

Example 1:

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

The graph has these edges:

```text
0 -> 1
0 -> 2
1 -> 3
2 -> 3
```

All paths from `0` to `3` are:

```python
[
    [0, 1, 3],
    [0, 2, 3],
]
```

Example 2:

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

The target is node `4`.

Valid paths include:

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

So the result is:

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

| Metric | Value | Why |
|---|---|---|
| Time | `O(P * n)` | Each saved path may contain up to `n` nodes |
| Space | `O(P * n)` | The output stores all paths |

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

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

```python
target = len(graph) - 1
```

We store all complete paths here:

```python
answer = []
```

The current path starts at source node `0`:

```python
path = [0]
```

When DFS reaches the target, we save a copy:

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

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

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

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

| Test | Why |
|---|---|
| Two simple paths | Checks branching from source |
| Larger DAG | Checks deeper paths and direct paths |
| Single edge | Smallest useful graph |
| Multiple parallel branches | Checks all neighbors are explored |