All Paths From Source to Target

MediumGraph DFS · Backtracking🧩 Graph DFS LeetCode #797 ↗Updated Oct 30, 2026

Problem

A directed acyclic graph with nodes 0..n-1 is given as an adjacency list: graph[i] lists the nodes reachable from i by one edge. Return every path that starts at node 0 and ends at node n - 1, each as the list of visited nodes. The paths may be returned in any order.

Inputgraph = [[1,2],[3],[3],[]]Output[[0,1,3],[0,2,3]]

Inputgraph = [[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]]

2 ≤ n ≤ 15 · graph[i] has distinct values, no self-loops · the graph is a DAG

Try it yourself

Java

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Because the graph has no cycles, no visited set is needed: any walk from 0 is automatically a simple path. Grow one shared path with DFS, snapshot it when you hit n - 1, and undo the last step on the way back.

PatternGraph DFS

Instinct Connected regions, all paths, reachability, cloning or 2-colouring a graph or grid: dive from a node, mark it, recurse into unvisited neighbours.

Memory hack Mark before you march: go deep, paint as you go, and back up only when every door is already painted.

Open the Graph DFS guide →

Approaches

Brute ForceBFS over Partial Paths

Time O(2ⁿ · n)Space O(2ⁿ · n)

Put the path [0] in a queue. Repeatedly take a path, and for each neighbour of its last node create a copy extended by that neighbour; copies ending at n - 1 are answers, the rest go back into the queue. Since the graph is acyclic, the process stops.

Java

public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
    int target = graph.length - 1;
    List<List<Integer>> res = new ArrayList<>();
    Queue<List<Integer>> queue = new ArrayDeque<>();
    queue.offer(new ArrayList<>(List.of(0)));
    while (!queue.isEmpty()) {
        List<Integer> path = queue.poll();
        int last = path.get(path.size() - 1);
        for (int next : graph[last]) {
            List<Integer> extended = new ArrayList<>(path); // copy per edge
            extended.add(next);
            if (next == target) res.add(extended);
            else queue.offer(extended);
        }
    }
    return res;
}

Correct and iterative, but every extension copies a path and a whole frontier of paths sits in memory at once.

OptimalDFS Backtracking with One Shared Path

Time O(2ⁿ · n)Space O(n) + output

Walk depth-first, appending each node to a single path list and removing it when the call returns. Only when the walk reaches n - 1 is the path copied into the answer. There can be up to 2^n-2 paths of length up to n, so the output size bounds any algorithm; this one adds only O(n) working memory.

Java

public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    path.add(0);
    dfs(graph, 0, path, res);
    return res;
}
private void dfs(int[][] graph, int node, List<Integer> path, List<List<Integer>> res) {
    if (node == graph.length - 1) {
        res.add(new ArrayList<>(path)); // snapshot a finished path
        return;
    }
    for (int next : graph[node]) {
        path.add(next);
        dfs(graph, next, path, res);
        path.remove(path.size() - 1); // backtrack
    }
}

Output-optimal time with just the recursion stack and one path as extra space.

Pro tip

If the graph could contain cycles you would need an onPath boolean array — mention that the DAG guarantee is what lets you drop it.

At a glance

Level	Approach	Time	Space
Brute Force	BFS over Partial Paths	`O(2ⁿ · n)`	`O(2ⁿ · n)`
Optimal	DFS Backtracking with One Shared Path	`O(2ⁿ · n)`	`O(n) + output`

Common pitfalls

Adding path itself to the result instead of a copy — every entry ends up empty.
Forgetting to remove the last node after the recursive call (no backtrack).
Starting with an empty path — node 0 must be the first element.

Interview tips

Point out that output can be exponential, so no algorithm beats O(2ⁿ·n).
Explain why the DAG property removes the need for a visited set.
Compare memory: BFS stores a frontier of full paths, DFS stores one path.

Pattern

DFS + backtracking on a DAG → enumerate all source-to-sink paths or combinations along edges.

My notes saved in this browser