Problem Breakdown
We are given a Directed Acyclic Graph (DAG) represented as an adjacency list where graph[i] contains the nodes reachable from node i. The goal is to find every possible path starting at source node 0 and ending exactly at target node n - 1.
Key Inputs & Outputs:
- Input: A list of lists (
graph) representing edges. Implicitly, . Source is always index0, Target is always indexn - 1. - Output: A list containing all valid paths from source to target. Each path is a sequence of node indices including start and end nodes.
Implicit Constraints & Edge Cases:
- Since it’s a DAG, we do not need cycle detection logic (like a visited set for preventing infinite loops), but the recursion depth must be bounded by .
- If there are no paths from
0ton - 1, return an empty list. - Constraints state , which suggests that while exponential time complexity is theoretically possible, it will fit within standard limits because the number of nodes is very small.
Intuition
A naive brute-force approach might try generating all permutations and checking validity, but that would be inefficient (). Since we are traversing a graph structure where edges dictate valid transitions, Depth-First Search (DFS) with backtracking is the natural fit.
We need to explore every branch from 0. When we hit a dead end or reach the target node:
- If it’s not the target and has no outgoing neighbors, backtrack immediately.
- If it is the target (
n - 1), record this path as valid.
Because we need to explore multiple branches from intermediate nodes (e.g., 0 -> A, then later 0 -> B), backtracking allows us to reuse a single list for the current path, adding and removing elements as we traverse down and up the recursion stack respectively. This avoids creating excessive memory overhead during traversal compared to passing new lists at every step.
Approach
- Initialize an empty list
resultto store all valid paths found. - Define a recursive helper function (or use nested scope) that takes the current node and the current path being built.
- Base Case: If the current node is equal to
n - 1, we have reached the target. We append a copy of the current path to our result list, then return immediately so we don’t continue traversing from the target (since it’s a DAG and has no outgoing edges in this context). - Recursive Step: Iterate through all neighbors defined by
graph[current_node]. For each neighbor:- Add the neighbor to the current path list.
- Recursively call the function with that neighbor.
- Backtrack: After returning from the recursive calls, remove the last added node from the current path list before continuing or exiting. This restores the state for exploring other branches originating from previous nodes.
Complexity Analysis
- Time Complexity: , where is the number of nodes and is the total number of valid paths found in the graph. In a dense DAG, the number of paths can grow exponentially (e.g., roughly proportional to Fibonacci numbers or Catalan structures depending on topology). However, given the constraint , this fits comfortably within time limits even for worst-case path counts.
- Space Complexity: for the recursion stack depth and the current
pathlist during traversal (excluding output storage). The space required to store the final result is proportional to the total number of paths times their average length, which dominates the auxiliary space complexity in terms of memory usage relative to input size.
Solution
class Solution:
def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
n = len(graph)
result = []
# Helper function for DFS traversal with backtracking
def dfs(node, current_path):
# Add current node to the path being built
current_path.append(node)
# Check if we have reached the target (n - 1)
if node == n - 1:
result.append(current_path[:]) # Append a copy of the path
# Explore all neighbors from the current node
for neighbor in graph[node]:
dfs(neighbor, current_path)
# Backtrack: remove the last added node to explore other branches
current_path.pop()
# Start DFS from source node 0 with an empty path list (will be appended immediately inside)
dfs(0, [])
return result
Edge Cases Handled
- Target Unreachable: If the graph structure prevents reaching
n - 1from0, the recursion completes without triggering the base case for target. The function returns an empty list naturally. - Direct Connection (Single Path): If there is only one edge , the loop runs once, hits the base case immediately, and records
[0, n-1]. Backtracking removesn-1, then pops0to finish cleanly. - Multiple Branches: The backtracking step (
pop()) ensures that when we return from a recursive call for one neighbor, the path list is restored to its state before entering that branch, allowing us to correctly process subsequent neighbors in the adjacency list of the same parent node.