LeetCode · #797

All Paths From Source to Target Solution

Given a directed acyclic graph graph where node 0 is the source and node n - 1 is the target, return every path from source to target.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #797

🏗️

Pattern

DFS — path enumeration on a DAG

You are given a graph as an adjacency list where graph[i] contains all nodes reachable from node i. The graph is guaranteed to be a DAG (directed acyclic graph). Return all paths that start at 0 and end at n - 1.

Example

 Input: graph = [[1,2],[3],[3],[]]
Output: [[0,1,3],[0,2,3]]
// Two valid source-to-target paths exist. 

Constraints

 • n == graph.length • 2 ≤ n ≤ 15 • 0 ≤ graph[i][j] < n • graph[i][j] > i for all valid j  ← edges go forward, so cycles cannot exist • The graph is guaranteed to be a DAG 

Section Two · Approach 1

DFS with Path Copying — O(P · L²)

Start DFS from node 0. For every outgoing edge, create a new copy of the current path, append the next node, and recurse. Whenever you reach target = n - 1, append that full path to the answer.

Why it works

Because the graph is acyclic, every recursive branch eventually stops. Copying the path for each branch isolates state, so sibling branches never interfere with one another.

Why we can do better

Problem: Copying the path list on every recursive edge adds extra O(L) work again and again. For one path of length L, you may copy prefixes of length 1, 2, 3, ... , L, which becomes O(L²) overhead per full path. We can reuse one shared path list and only copy when we actually emit a complete answer.

Java — DFS with cloned path per branch

 import java.util.*;
class Solution {
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> start = new ArrayList<>();
        start.add(0);
dfs(graph, 0, graph.length - 1, start, result);
return result;
    }
private void dfs(int[][] graph, int node, int target,
List<Integer> path,
List<List<Integer>> result) {
if (node == target) {
            result.add(path);
return;
        }
for (int next : graph[node]) {
List<Integer> nextPath = new ArrayList<>(path);
            nextPath.add(next);
dfs(graph, next, target, nextPath, result);
        }
    }
}

Python — DFS with copied path lists

 class Solution:
def allPathsSourceTarget(self, graph: list[list[int]]) -> list[list[int]]:
        result = []
        target = len(graph) - 1 def dfs(node: int, path: list[int]) -> None:
if node == target:
                result.append(path)
return for nxt in graph[node]:
                dfs(nxt, path + [nxt])

        dfs(0, [0])
return result

Metric	Value
Time	O(P · L²) in the worst case due to repeated path copying
Space	O(L) recursion stack, excluding output

Section Three · Approach 2

Backtracking DFS with One Shared Path — O(P · L)

Keep one mutable path list. Start with [0]. When exploring an edge node → next, append next, recurse, then pop it after returning. Only when we reach the target do we copy the path into the answer list.

💡 Mental model: Think of walking a maze while carrying one whiteboard that shows your current route. When you move forward, you write the next room on the board. When a branch is finished, you erase that room and try another branch. You do not print a new whiteboard for every turn; you only take a photograph when you reach the exit. That photograph is the copied answer path.

Algorithm — DFS path backtracking on a DAG

Initialize: set target = n - 1, path = [0], and result = [].
DFS(node): if node == target, copy path into result and return.
Explore neighbors: for each next in graph[node], append it to path, recurse, then remove it after returning.
No visited set needed: the graph is a DAG, so DFS cannot loop forever.
Copy only at leaves: never store the live path object directly in result.

🎯 Recognition signal:

If the problem asks for all paths, all combinations, or all valid sequences, DFS + backtracking is usually the right pattern.
For this problem specifically, the word DAG is a huge clue that recursion can safely enumerate every branch without cycle handling.

No visited set here — and that is correct:

In a general directed graph, a visited/path-state structure is necessary to avoid infinite recursion on cycles.
But LC 797 guarantees acyclicity, so a visited set would be extra work and can even be conceptually misleading.
The only state we need is the current path.

Section Four · Trace

Visual Walkthrough

Trace the DFS on graph = [[1,2],[3],[3],[]]. There are exactly two source-to-target paths.

All Paths From Source to Target — DFS Backtracking Trace

Section Five · Implementation

Code — Java & Python

Java — DFS backtracking on one shared path

 import java.util.*;
class Solution {
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
        path.add(0);
dfs(graph, 0, graph.length - 1, path, result);
return result;
    }
private void dfs(int[][] graph, int node, int target,
List<Integer> path,
List<List<Integer>> result) {
if (node == target) {
            result.add(new ArrayList<>(path));
return;
        }
for (int next : graph[node]) {
            path.add(next); // choose dfs(graph, next, target, path, result);
            path.remove(path.size() - 1); // unchoose
}
    }
}

Python — DFS backtracking with append/pop

 class Solution:
def allPathsSourceTarget(self, graph: list[list[int]]) -> list[list[int]]:
        result = []
        target = len(graph) - 1
path = [0]
def dfs(node: int) -> None:
if node == target:
                result.append(path[:])
return for nxt in graph[node]:
                path.append(nxt) # choose
dfs(nxt)
                path.pop() # unchoose
dfs(0)
return result

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
DFS + copied path each branch	O(P · L²)	O(L) recursion, excluding output	Simple to reason about, but wastes time re-copying path prefixes.
Backtracking DFS ← optimal	O(P · L)	O(L) recursion, excluding output	Only copies the path once per completed answer, which matches the unavoidable output size.

What do P and L mean?:

P is the number of valid source-to-target paths, and L is the maximum path length.
Since the output itself contains P paths of length up to L, any correct solution must spend at least O(P · L) time just to write the answer down.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Expected behavior	Why it matters
Single direct path	`[[1],[]]` → `[[0,1]]`	The base case is reached immediately after one recursive step.
Multiple branches	Return every valid path	DFS must continue exploring after recording the first answer.
Dead-end node before target	That branch returns without adding anything	Not every path prefix necessarily reaches `n - 1`.
No visited set	Still correct for LC 797	The graph is guaranteed to be acyclic, so recursion cannot loop forever.
Store live path reference	Wrong / mutated answers	You must copy `path` at the target, or all stored results will later change together.

⚠ Common Mistake: Doing result.add(path) in Java or result.append(path) in Python at the target. That stores the same mutable list object. After backtracking pops elements, every stored answer changes too. Always save a copy: new ArrayList<>(path) or path[:].

← Back to DFS problems

LearningTree

LC 797 · All Paths From Source to Target — Solution & Explanation | DSA Guide