Domain 2MediumMEDIUM

All Paths From Source to Target

LeetCode problem 797: All Paths From Source to Target (medium).

Domain: medium•Updated: 2026-09-01
#Backtracking#Depth-first Search#Graph

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, n=len(graph)n = \text{len(graph)}. Source is always index 0, Target is always index n - 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 nn.
  • If there are no paths from 0 to n - 1, return an empty list.
  • Constraints state N≤15N \le 15, 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 (O(N!)O(N!)). 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:

  1. If it’s not the target and has no outgoing neighbors, backtrack immediately.
  2. 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

  1. Initialize an empty list result to store all valid paths found.
  2. Define a recursive helper function (or use nested scope) that takes the current node and the current path being built.
  3. 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).
  4. 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.
  5. 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: O(N⋅P)O(N \cdot P), where NN is the number of nodes and PP 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 N≤15N \le 15, this fits comfortably within time limits even for worst-case path counts.
  • Space Complexity: O(N)O(N) for the recursion stack depth and the current path list 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 - 1 from 0, 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 0→n−10 \to n-1, the loop runs once, hits the base case immediately, and records [0, n-1]. Backtracking removes n-1, then pops 0 to 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.