All Paths From Source to Target — Solution

Problem

Given a directed acyclic graph (DAG) with n nodes numbered 0 through n−1, find every possible path from node 0 to node n−1. The graph is given as an adjacency list where graph[i] lists the nodes that node i has an outgoing edge to.

• Input: graph = [[1,2],[3],[3],[]]
• Output: [[0,1,3],[0,2,3]]
• Explanation: From node 0 you can branch to node 1 or 2; both routes reach the destination node 3.

Intuition

Because the graph is a DAG (no cycles), every path from node 0 must eventually terminate — it can never loop back to a node it already visited. This means we can explore every branch freely with depth-first search, recording a snapshot of the path each time we land on node n−1, and simply pop the last node to backtrack when a branch is exhausted.

Solution — DFS with Backtracking

Extend the current path one node at a time; when the path reaches node n−1, record a copy of it. Because the graph has no cycles, no visited set is needed.

1. Initialize results = [] and seed current_path = [0] with the source node.
2. Call dfs(0) to start exploration from node 0.
3. In dfs(node): if node == n − 1, append a copy of current_path to results and return.
4. For each neighbor in graph[node], append neighbor to current_path, recurse into dfs(neighbor), then pop neighbor to backtrack.
5. Return results after the initial call completes.

1def allPathsSourceTarget(graph: list[list[int]]) -> list[list[int]]:
2    results = []
3    current_path = [0]  # seed with source so it appears in every recorded path
4
5    def dfs(node: int) -> None:
6        if node == len(graph) - 1:          # reached the destination
7            results.append(list(current_path))  # snapshot — not a reference
8            return
9        for neighbor in graph[node]:
10            current_path.append(neighbor)
11            dfs(neighbor)
12            current_path.pop()              # backtrack before trying next neighbor
13
14    dfs(0)
15    return results

Time: O(2^n · n) — a complete DAG can have up to 2^(n−2) distinct paths, and copying each path of length n costs O(n).
Space: O(2^n · n) for the stored results; the recursion stack grows at most O(n) deep since the graph is a DAG.

Complexity Summary

Common Mistakes

• Storing a reference instead of a snapshot — results.append(current_path) adds the same mutable list every time; by the end, every entry points to an empty list. Use results.append(list(current_path)) to capture the state at that moment.
• Adding a visited set — because the graph is a DAG, no node can be revisited on any single path; a visited set wastes memory and introduces bugs if it mistakenly blocks legitimate paths shared by different routes.
• Forgetting to seed current_path with node 0 — if the initial call to dfs starts with an empty path, every recorded result will be missing the source node.
• Hardcoding the destination index — checking node == n - 1 with a separate variable n set outside the function is fragile; use len(graph) - 1 directly so the code is self-contained for any input.
• Omitting the pop after recursion — without the backtrack step, stale neighbors accumulate in current_path across sibling branches, corrupting every path recorded after the first.

Related Problems

• path-sum-ii — same collect-all-paths-via-backtracking pattern, applied to a binary tree instead of a graph
• word-search — DFS with backtracking on a 2D grid where the path must be pruned and restored at each step
• course-schedule — DFS on a directed adjacency list, but the goal is cycle detection rather than path enumeration
• number-of-islands — DFS/BFS graph exploration where reachability (not paths) is the objective
• clone-graph — DFS traversal of an adjacency list to deeply copy an arbitrary graph structure