Coding Interview PatternsAll Paths From Source to Target
MediumGraphs

All Paths From Source to Target

Explanation & Solution

Practice Problem

Description

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 an adjacency list where 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 each node in graph[i]).

Examples

Example 1

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

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

Explanation: There are two paths from node 0 to node 3: 0 → 1 → 3 and 0 → 2 → 3.

Example 2

Input: 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]]

Explanation: There are five paths from node 0 to node 4.

Constraints

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

Approach

Graphs pattern

1. Set Up DFS with Backtracking

  • Define the target as node n - 1 (the last node).
  • Start a DFS from node 0 with an initial path of [0].
  • Maintain a results array to collect all valid paths.

2. Explore Neighbors Recursively

  • At each node, iterate over its neighbors in graph[node].
  • Push the neighbor onto the current path and recurse into it.
  • After returning from the recursive call, pop the neighbor off the path (backtrack).

3. Collect Complete Paths

  • When the current node equals the target, copy the current path into the results array.
  • Since the graph is a DAG, there are no cycles, so every DFS branch will eventually terminate.

Key Insight

  • Because the graph is a DAG, we do not need a visited set — there are no cycles to worry about. Simple DFS with backtracking naturally explores every possible route from source to target. Pushing and popping from a single path array avoids creating unnecessary copies until a complete path is found.

Visualization

Input:
DFS Traversal4 nodes, 4 edges
0123
output—

Press play to start dfs traversal

CurrentQueuedVisited
16 steps

Solution Code

Previous
Reorder Routes to Make All Paths Lead to City Zero
Next
Minimum Height Trees