All Paths from Source to Target — DFS with Backtracking

Problem Statement#

LeetCode 797 — All Paths From Source to Target (Medium)

Given a directed acyclic graph (DAG) of n nodes labeled from 0 to n - 1, find all possible paths from node 0 to node n - 1 and return them in any order.

The graph is given as follows: graph[i] is a list of all nodes you can visit from node i (i.e., there is a directed edge from node i to node graph[i][j]).

Constraints:

• n == graph.length
• 2 <= n <= 15
• 0 <= graph[i][j] smaller than n
• graph[i][j] != i (no self-loops)
• All elements of graph[i] are unique.
• The graph is guaranteed to be a DAG.

Example 1:

graph = [[1,2],[3],[3],[]]
Output: [[0,1,3],[0,2,3]]

Example 2:

graph = [[4,3,1],[3,2,4],[3],[4],[]]
Output: [[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

Why This Problem Matters#

All Paths from Source to Target is the textbook DFS plus backtracking problem, frequently asked at Amazon, Google, and Meta as a warm-up before harder enumeration questions like LC 980 (Unique Paths III) and LC 1255 (Maximum Score Words). It tests whether you can:

1. Recognize an enumeration problem. "Find all paths" means you cannot prune by best-cost or visited-once. You must explore every branch.
2. Manage a path stack correctly. Push on entry, pop on backtrack, snapshot on success.
3. Exploit DAG structure. Because there are no cycles, you do not need a visited set — every path naturally terminates.

The DAG guarantee is critical. In a general directed graph with cycles, the same algorithm could spin forever. Mentioning this in the interview signals graph maturity.

The Core Insight#

DFS from node 0 carrying a current path. On each call:

• If current node is n - 1, append a copy of the path to the result.
• Otherwise, for every neighbor, push neighbor onto the path, recurse, then pop.

Because the graph is a DAG, no neighbor can revisit an earlier ancestor in the path, so cycles are impossible. No visited set is needed. This is one of the few graph problems where you can drop the visited check safely.

The output size can be exponential. With n <= 15 and a fully connected DAG, the number of paths can reach 2 to the (n - 1) = 16,384, which is manageable. The constraint n <= 15 is exactly tuned to allow exhaustive enumeration.

A subtle implementation detail: append a copy of the path, not the path reference. If you push the live path object, mutating it later corrupts the saved result.

Visual Dry Run#

graph = [[1,2],[3],[3],[]]. DFS from 0:

path = [0]   neighbors of 0 = [1, 2]
 
Recurse with path = [0, 1]   neighbors of 1 = [3]
  Recurse with path = [0, 1, 3]   3 == n-1 -> snapshot [0,1,3]
  Backtrack: path = [0, 1]
Backtrack: path = [0]
 
Recurse with path = [0, 2]   neighbors of 2 = [3]
  Recurse with path = [0, 2, 3]   3 == n-1 -> snapshot [0,2,3]
  Backtrack: path = [0, 2]
Backtrack: path = [0]
 
Result: [[0,1,3], [0,2,3]]

Notice the perfect symmetry: every push has a matching pop, ensuring the path stack returns to its caller in its original state.

Solution (Optimal)#

Python (DFS with explicit backtracking)#

class Solution:
    def allPathsSourceTarget(self, graph: list[list[int]]) -> list[list[int]]:
        n = len(graph)
        target = n - 1
        result: list[list[int]] = []
        path: list[int] = [0]                        # start path with source
 
        def dfs(node: int) -> None:
            if node == target:
                result.append(path.copy())           # snapshot current path
                return
            for nxt in graph[node]:                  # explore each out-edge
                path.append(nxt)                     # push (descend)
                dfs(nxt)
                path.pop()                            # pop (backtrack)
 
        dfs(0)
        return result

JavaScript (Same algorithm, idiomatic JS)#

/**
 * @param {number[][]} graph
 * @return {number[][]}
 *
 * DFS plus backtracking. No visited set needed because the graph is a DAG.
 */
var allPathsSourceTarget = function(graph) {
    const n = graph.length;
    const target = n - 1;
    const result = [];
    const path = [0];                                // start at source
 
    const dfs = (node) => {
        if (node === target) {
            result.push([...path]);                  // snapshot the current path
            return;
        }
        for (const nxt of graph[node]) {
            path.push(nxt);                          // descend
            dfs(nxt);
            path.pop();                               // backtrack
        }
    };
 
    dfs(0);
    return result;
};

Complexity. Time is O(2 to the n times n) in the worst case for a fully connected DAG, where each path can be up to length n. Space is O(n) for the recursion stack and current path, plus O(P times n) for the output where P is the number of paths.

Common Mistakes#

1. Pushing the path reference instead of a copy. result.append(path) saves a reference, and subsequent mutations corrupt all stored paths. Always copy.
2. Adding a visited set unnecessarily. Because the graph is a DAG, a visited set is redundant and might even be wrong if a node can be reached via multiple distinct paths (which is the whole point).
3. Forgetting to backtrack (pop). Skipping the pop leaves stale nodes on the path, producing wrong outputs and mysterious bugs.
4. Iterative BFS for enumeration. BFS over paths technically works but uses much more memory because every prefix in the queue is its own list. DFS reuses one path stack.
5. Returning early after finding one path. The problem asks for all paths, not just one.

Interview Tips#

• State the DAG observation explicitly. "Because the graph is a DAG, I do not need a visited set — every path naturally terminates." This single sentence shows graph fluency.
• Mention the exponential output size. Saying "the worst case has 2 to the (n - 1) paths, so any algorithm is bounded below by output size" demonstrates complexity awareness.
• Use the snapshot trick. Always copy the path on success. Calling out this detail prevents the most common bug.
• Discuss BFS as an alternative. "BFS could enumerate paths too but uses more memory; DFS shares one path stack via push/pop." This is a tier-up answer.

Follow-up Questions#

1. Cyclic graph instead of DAG. Add a visited set per path (not global) so you do not revisit nodes within the same path. Still potentially exponential.
2. Count paths only, do not list them. Use DFS with memoization on each node — dp[node] = sum of dp[neighbor]. O(V + E) instead of exponential.
3. Shortest path among all paths. BFS with parent tracking; reconstruct the parent chain once you reach the target.
4. Top-K shortest paths. Use Yen algorithm or repeated Dijkstra with edge removal.
5. Paths visiting all nodes (Hamiltonian). That is LC 980 and LC 943 — bitmask DP on the visited set.

Key Takeaways#

• All Paths from Source to Target is the canonical DFS plus backtracking enumeration problem.
• Because the graph is a DAG, no visited set is required — cycles are impossible.
• Always copy the path when snapshotting; never store a reference.
• Push on enter, pop on backtrack — perfect symmetry around the recursive call.
• Output can be exponential, hence the small n <= 15 constraint.
• Counting paths becomes polynomial via memoization; listing them remains exponential.