All Paths from Source to Target

Find every possible path from node 0 to node n-1 in a directed acyclic graph.

graph dfs backtracking acyclic

You are given a directed acyclic graph (DAG) with n nodes labeled from 0 to n-1. The graph is represented by a list `graph` of length n, where `graph[i]` is a list of nodes that node i has edges to. Write a function `all_paths_source_target(graph)` that returns a list of all paths from node 0 to node n-1 in any order. Each path is a list of node labels starting with 0 and ending with n-1. The graph is guaranteed to be a DAG (no cycles), so paths can be generated by simple depth-first search without worrying about infinite recursion. The order of paths in the output does not matter, and the order of nodes within a path must follow the edges.

Constraints

- 1 <= n <= 15
- The graph is a DAG.
- Each node's adjacency list contains integers between 0 and n-1.
- At least one path from 0 to n-1 exists? Not guaranteed, but if none, return an empty list.
- The total number of paths is at most 2^15 (fits in memory).
- Time complexity: O(2^n) in worst case, which is acceptable for n<=15.

Example

>>> all_paths_source_target([[1,2],[3],[3],[]])
[[0,1,3],[0,2,3]]
>>> all_paths_source_target([[1],[]])
[[0,1]]
>>> all_paths_source_target([[1,2,3],[2],[3],[]])
[[0,1,2,3],[0,2,3],[0,3]]

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Try a depth-first search from node 0.

Keep track of the current path and add it to the result when you reach the last node (n-1).

Because the graph is a DAG, you don't need to mark visited nodes — but you can if you like.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.