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]).
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]]
Constraints:
n == graph.length2 <= n <= 150 <= graph[i][j] < ngraph[i][j] != i (i.e., there will be no self-loops).graph[i] are unique.Problem Overview: You are given a directed acyclic graph (DAG) represented as an adjacency list. Starting from node 0, find every possible path that ends at node n-1. Each path must follow the directed edges of the graph and the result should include all valid sequences of nodes from source to target.
The graph is guaranteed to be acyclic, which means no node will be revisited in the same path. The main challenge is enumerating every valid path efficiently without missing combinations.
Approach 1: Depth First Search (DFS) with Backtracking (Time: O(P * N), Space: O(N))
This approach performs a depth-first traversal from the source node. Maintain a path list representing the current traversal. At each node, iterate through its neighbors and recursively explore them. When the traversal reaches node n-1, copy the current path into the result list.
Backtracking is the key idea: after exploring a neighbor, remove it from the path before moving to the next option. Because the graph is a DAG, there is no need for a visited set in the recursion stack. The time complexity depends on the number of valid paths P and the maximum path length N, giving O(P * N). Recursion depth and path storage require O(N) auxiliary space.
This method is the most natural way to enumerate paths and commonly appears in problems involving Backtracking and Depth-First Search. It is typically the expected interview solution.
Approach 2: Breadth First Search (BFS) with Path Expansion (Time: O(P * N), Space: O(P * N))
The BFS strategy builds paths level by level using a queue. Each queue entry stores an entire partial path instead of a single node. Start by pushing [0] into the queue. At each step, remove the front path, look at its last node, and extend the path with every neighbor.
If the last node equals n-1, the path is complete and added to the result. Otherwise, the extended paths are pushed back into the queue for further exploration. This effectively performs a layer-by-layer traversal of all possible path prefixes.
The algorithm still explores every valid path, so the time complexity remains O(P * N). However, BFS stores many partial paths simultaneously, leading to higher memory usage of O(P * N). The approach is useful when solving similar path enumeration problems using Breadth-First Search on a Graph structure.
Recommended for interviews: DFS with backtracking is the preferred solution. It uses minimal memory, expresses the recursive structure of path exploration clearly, and is the approach most interviewers expect. BFS demonstrates strong understanding of path expansion in graphs but consumes more memory because every partial path must be stored in the queue.
The Depth First Search (DFS) approach uses a recursive function to explore all paths from the source node to the target node by traversing each possible node in a depth-first manner. This involves exploring as far as possible along each branch before backing up.
This C solution implements a depth-first search (DFS) recursively. The function "dfs" is called with each node and adds the node to the current path. If the current node is the target node, the path is added to the result. Otherwise, the function is called recursively for each of the node's children. Memory is dynamically allocated for the paths and adjusted for recursion depth.
Time Complexity: O(2^n) - since every node could lead to every other node, creating exponential paths.
Space Complexity: O(n) - the maximum depth of the recursion, and path storage could be O(n) as well.
The Breadth First Search (BFS) approach uses a queue to explore nodes level by level, tracking each path as it progresses. This is an iterative process that can make finding all possible paths easier to visualize compared to recursive methods like DFS.
This C solution implements Breadth First Search (BFS) using a queue to iteratively explore the graph level by level. Paths are stored in the queue and processed in FIFO order. New paths are generated for each child node, leading to either an extension to the path or storing the path if it reaches the target node.
Time Complexity: O(2^n) - Because each node may lead to different paths creating an exponential number of routes.
Space Complexity: O(2^n) - Required for holding all potential paths in the queue.
| Approach | Complexity |
|---|---|
| Depth First Search (DFS) Approach | Time Complexity: O(2^n) - since every node could lead to every other node, creating exponential paths. |
| Breadth First Search (BFS) Approach | Time Complexity: O(2^n) - Because each node may lead to different paths creating an exponential number of routes. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS with Backtracking | O(P * N) | O(N) | Best general solution for enumerating all paths in a DAG. Low memory usage and preferred in interviews. |
| BFS with Path Expansion | O(P * N) | O(P * N) | Useful when exploring paths level-by-level or adapting BFS templates for path generation problems. |
Graph Coding Question - All Paths From Source To Target (LeetCode) • AlgosWithMichael • 43,372 views views
Watch 9 more video solutions →Practice All Paths From Source to Target with our built-in code editor and test cases.
Practice on FleetCode