Skip to main content

797. All Paths From Source to Target

medium

Return every path from node 0 to node n-1 in a directed acyclic graph. Pure recursive DFS path enumeration — no revisit guard needed because the graph is a DAG.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

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] < n
  • graph[i][j] != i (i.e., there will be no self-loops).
  • All the elements of graph[i] are unique.
  • The input graph is guaranteed to be a DAG.

Examples

Example 1

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

Explanation: There are two paths: 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]]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

DFS from node 0. Carry the current path.

Hint 2

Base case: current node == n - 1 -> snapshot path.

Hint 3

For each neighbor, append, recurse, pop.

Hint 4

No visited set needed — it's a DAG, no cycles.

Solution approach

Reveal approach

Recursive DFS with backtracking. dfs(node, path): push node onto path. If node == n - 1, snapshot path to result. Otherwise for each next in graph[node], dfs(next, path). Pop node from path. Start with dfs(0, []). Because the graph is acyclic, no visited set is needed — every recursive call descends strictly toward n - 1. Time is O(2^n * n) worst case (the total number of paths in a DAG can be exponential in n; copying each path of length up to n contributes the n factor). Space is O(n) recursion depth plus output.

Complexity

Time
O(2^n * n)
Space
O(n)

Related patterns

  • recursion
  • dfs
  • backtracking

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google

More Recursion practice problems

See all Recursion problems →