Asked at

All Paths From Source to Target

Medium
VerifiedDFSBacktrackingGraph~20 min

You’re given a directed acyclic graph of n nodes 0..n-1 as an adjacency list: graph[i] is the list of nodes that node i points to. The input is this number[][] directly.

Return all paths from node 0 to node n - 1. Paths may be returned in any order.

Examples

in[[1,2],[3],[3],[]]
out[[0,1,3],[0,2,3]]

Two ways to reach node 3 from node 0.

in[[1],[]]
out[[0,1]]

The only path is the single edge 0→1.

Constraints

  • 2 ≤ n ≤ 15
  • graph is a DAG given as an adjacency list.
  • graph[i] lists the nodes i points to (directed).
  • The graph contains no self-loops.

Get help

🔑

Sign in to solve

Sign in to write, run, and submit your solution — and to pick up where your iOS flow left off.