LeetCode 797 - All Paths From Source to Target

LeetCode Problem 797

Difficulty: 🟡 Medium
Topics: Backtracking, Depth-First Search, Breadth-First Search, Graph Theory

Solution

Problem Understanding

The problem gives us a directed acyclic graph, usually abbreviated as a DAG. The graph contains n nodes labeled from 0 to n - 1. The graph is represented as an adjacency list, where graph[i] contains all nodes that can be reached directly from node i.

Our task is to find every possible path that starts at node 0 and ends at node n - 1. Each path should be represented as a list of node values, and the final answer is a list containing all valid paths.

For example, if the graph is:

0 -> 1 -> 3
 \-> 2 -> 3

then the valid paths from 0 to 3 are:

[[0, 1, 3], [0, 2, 3]]

The graph is guaranteed to be a DAG, which is extremely important. A DAG contains no cycles, meaning we can never revisit the same node infinitely while traversing forward. This guarantee allows us to safely perform depth-first traversal without needing cycle detection logic.

The constraints are relatively small:

• 2 <= n <= 15

Even though the number of nodes is small, the number of possible paths can still grow exponentially. In a DAG, many different combinations of edges can create many valid source-to-target paths.

The important observations from the constraints are:

• The graph is directed.
• The graph has no cycles.
• We must return all valid paths, not just count them.
• The answer size itself may be exponential.

Several edge cases are worth considering:

• A graph where there is only one path from source to target.
• A graph where the source connects directly to the target.
• A graph with heavy branching, producing many valid paths.
• A graph where intermediate nodes have no outgoing edges except along valid paths.
• Since the graph is guaranteed to be a DAG, we never need to handle infinite recursion caused by cycles.

Approaches

Brute Force Approach

The most straightforward idea is to generate every possible path starting from node 0. At each node, we try every outgoing edge and continue recursively until we either reach the target node or run out of edges.

This brute-force idea already resembles depth-first search because we must explore every possible route. Since the problem explicitly asks for all paths, we cannot avoid exploring all valid combinations.

A naive implementation might repeatedly copy entire paths at every recursive call, creating unnecessary overhead. It may also use inefficient traversal structures that increase memory usage.

The brute-force approach is correct because every path from the source is explored recursively, and every time we reach the target node we record the current path.

However, the total number of paths in a DAG can be exponential. In the worst case, we may need to enumerate an enormous number of valid paths.

Key Insight for the Optimal Solution

The key insight is that this problem naturally fits recursive depth-first search with backtracking.

Why?

Because each path is built incrementally:

• Start from node 0
• Choose a neighbor
• Continue exploring
• Undo the choice when returning

This exactly matches the backtracking pattern.

Since the graph is a DAG:

• We never revisit nodes in a cycle
• Recursive DFS is safe
• Every recursive call represents one partial path

The optimal solution maintains a single mutable path during traversal. Instead of creating a new path object at every step, we:

1. Add a node to the current path
2. Explore recursively
3. Remove the node afterward

This minimizes unnecessary copying while still generating all valid paths correctly.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n * n)	O(2^n * n)	Generates all possible paths with excessive path copying
Optimal DFS + Backtracking	O(2^n * n)	O(n) excluding output	Efficient recursive traversal with backtracking

The output itself may contain exponentially many paths, so no algorithm can fundamentally avoid exponential work in the worst case.

Algorithm Walkthrough

Optimal DFS + Backtracking Algorithm

1. Initialize an empty result list that will store all valid paths from source to target.
2. Create a recursive DFS function that accepts:

• The current node
• The current path being explored

3. Start the traversal from node 0 with the initial path [0].
4. Inside the DFS function, first check whether the current node is the target node n - 1.

If it is:

• Append a copy of the current path to the result list.
• Return immediately because this path is complete.

5. Otherwise, iterate through all neighbors of the current node.
6. For each neighbor:

• Add the neighbor to the current path.
• Recursively continue DFS from that neighbor.
• After recursion finishes, remove the neighbor from the path.

This removal step is the backtracking step. It restores the path to its previous state so the next neighbor can be explored independently. 7. Continue until all recursive calls complete. 8. Return the result list containing all discovered paths.

Why it works

The algorithm maintains the invariant that path always represents the exact sequence of nodes from the source to the current DFS node.

Because the graph is acyclic, recursive traversal can never loop infinitely. Every possible directed path from source to target is explored exactly once. Whenever the traversal reaches the target node, the current path is a valid solution and is added to the result.

Backtracking ensures that after exploring one branch, the path state is restored correctly before exploring the next branch.

Python Solution

from typing import List

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        target = len(graph) - 1
        result = []

        def dfs(node: int, path: List[int]) -> None:
            if node == target:
                result.append(path[:])
                return

            for neighbor in graph[node]:
                path.append(neighbor)
                dfs(neighbor, path)
                path.pop()

        dfs(0, [0])

        return result

The implementation begins by identifying the target node, which is always n - 1.

The result list stores all valid paths discovered during traversal.

The recursive dfs function performs the core traversal logic. The path variable contains the current traversal route from source to the current node.

When the current node equals the target, we append a copy of the current path to the result list. We use path[:] because path is mutable and will continue changing during backtracking.

The loop over graph[node] explores every outgoing edge. Before recursion, the neighbor is appended to the path. After recursion finishes, the neighbor is removed using pop().

This append-recursion-pop pattern is the standard backtracking structure.

Finally, DFS starts from node 0 with the initial path [0].

Go Solution

func allPathsSourceTarget(graph [][]int) [][]int {
	target := len(graph) - 1
	result := [][]int{}

	var dfs func(int, []int)

	dfs = func(node int, path []int) {
		if node == target {
			pathCopy := make([]int, len(path))
			copy(pathCopy, path)
			result = append(result, pathCopy)
			return
		}

		for _, neighbor := range graph[node] {
			path = append(path, neighbor)
			dfs(neighbor, path)
			path = path[:len(path)-1]
		}
	}

	dfs(0, []int{0})

	return result
}

The Go implementation follows the same recursive DFS and backtracking strategy as the Python version.

One important Go-specific detail is slice copying. Slices in Go share underlying arrays, so we must explicitly create a new slice before appending a completed path to result. This is done using:

pathCopy := make([]int, len(path))
copy(pathCopy, path)

Without this copy, later modifications during backtracking would alter previously stored paths.

Go slices are dynamically resized, making them suitable for maintaining the current traversal path.

Since node values are small integers and constraints are small, integer overflow is not a concern.

Worked Examples

Example 1

Input:

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

Graph structure:

0 -> 1 -> 3
 \-> 2 -> 3

Target node is 3.

Step-by-step traversal

Step	Current Node	Current Path	Action
1	0	[0]	Start DFS
2	1	[0,1]	Explore neighbor 1
3	3	[0,1,3]	Reached target, save path
4	1	[0,1]	Backtrack
5	0	[0]	Backtrack
6	2	[0,2]	Explore neighbor 2
7	3	[0,2,3]	Reached target, save path
8	2	[0,2]	Backtrack
9	0	[0]	DFS complete

Final result:

[[0, 1, 3], [0, 2, 3]]

Example 2

Input:

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

Graph structure:

0 -> 4
0 -> 3 -> 4
0 -> 1 -> 3 -> 4
0 -> 1 -> 2 -> 3 -> 4
0 -> 1 -> 4

Traversal summary

Current Path	Result Added?
[0,4]	Yes
[0,3,4]	Yes
[0,1,3,4]	Yes
[0,1,2,3,4]	Yes
[0,1,4]	Yes

Final result:

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

Complexity Analysis

Measure	Complexity	Explanation
Time	O(2^n * n)	Number of paths may be exponential, each path copy costs O(n)
Space	O(n) excluding output	Recursive stack and current path length are bounded by n

The dominant factor is the number of valid paths in the DAG. In the worst case, a DAG can contain exponentially many source-to-target paths.

Every valid path must eventually be copied into the result array, and each copy costs proportional to the path length. Therefore, the total runtime becomes:

(number of paths) * (average path length)

The recursive stack depth is at most n, because the graph is acyclic and no node can appear twice in a single path.

The output storage itself is not included in the auxiliary space complexity because it is required by the problem.

Test Cases

from typing import List

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        target = len(graph) - 1
        result = []

        def dfs(node: int, path: List[int]) -> None:
            if node == target:
                result.append(path[:])
                return

            for neighbor in graph[node]:
                path.append(neighbor)
                dfs(neighbor, path)
                path.pop()

        dfs(0, [0])

        return result

solution = Solution()

# Example 1
assert solution.allPathsSourceTarget(
    [[1, 2], [3], [3], []]
) == [[0, 1, 3], [0, 2, 3]]  # basic branching graph

# Example 2
assert solution.allPathsSourceTarget(
    [[4, 3, 1], [3, 2, 4], [3], [4], []]
) == [
    [0, 4],
    [0, 3, 4],
    [0, 1, 3, 4],
    [0, 1, 2, 3, 4],
    [0, 1, 4]
]  # multiple valid paths

# Single direct path
assert solution.allPathsSourceTarget(
    [[1], []]
) == [[0, 1]]  # smallest valid graph

# Linear chain
assert solution.allPathsSourceTarget(
    [[1], [2], [3], []]
) == [[0, 1, 2, 3]]  # only one possible path

# Multiple branching levels
assert solution.allPathsSourceTarget(
    [[1, 2], [3, 4], [4], [5], [5], []]
) == [
    [0, 1, 3, 5],
    [0, 1, 4, 5],
    [0, 2, 4, 5]
]  # deeper branching DAG

# Source directly connected to target plus longer route
assert solution.allPathsSourceTarget(
    [[1, 2], [2], []]
) == [
    [0, 1, 2],
    [0, 2]
]  # direct and indirect paths coexist

Test	Why
[[1,2],[3],[3],[]]	Validates standard branching traversal
[[4,3,1],[3,2,4],[3],[4],[]]	Validates many overlapping path combinations
[[1],[]]	Smallest valid input
[[1],[2],[3],[]]	Ensures linear traversal works correctly
[[1,2],[3,4],[4],[5],[5],[]]	Tests deeper recursive branching
[[1,2],[2],[]]	Verifies direct and indirect paths both appear

Edge Cases

Direct Connection from Source to Target

A graph may contain an immediate edge from node 0 to node n - 1.

Example:

[[1], []]

This is easy to mishandle if the algorithm assumes at least one intermediate node exists. The implementation handles this naturally because the DFS immediately reaches the target and records the path.

Graph with Only One Valid Path

Some DAGs form a simple chain:

0 -> 1 -> 2 -> 3

There is no branching at all. A buggy implementation might incorrectly rely on multiple recursive branches or mishandle path copying. The recursive DFS still works correctly because each node simply has one outgoing neighbor.

Heavy Branching Producing Many Paths

A DAG can contain many overlapping branches, causing the number of valid paths to grow exponentially.

This stresses both correctness and backtracking behavior. If the path is not properly restored after recursion, paths can become corrupted or contain extra nodes.

The implementation avoids this issue by always using:

path.append(neighbor)
dfs(neighbor, path)
path.pop()

This guarantees the path state is restored correctly after each recursive exploration.