All Paths From Source to Target

Find all possible paths from source node to target node in a directed acyclic graph (DAG)

Language Selection

Choose your preferred programming language

Showing: Python

All Paths From Source to Target

Problem Statement

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 represented as an adjacency list where graph[i] is a list of all nodes you can visit from node i.

Input/Output Specifications

Input: A directed acyclic graph represented as an adjacency list graph[][]
Output: A list of all paths from node 0 to node n-1, where each path is represented as a list of node numbers

Constraints

n == graph.length
2 <= n <= 15
0 <= graph[i][j] < n
graph[i][j] != i (no self-loops)
All elements of graph[i] are unique
The input graph is guaranteed to be a DAG

Examples

Example 1:

Input: graph = [[1,2],[3],[3],[]]
Output: [[0,1,3],[0,2,3]]
Explanation: 
Graph: 0 -> 1 -> 3
       |    |
       v    v
       2 -> 3
There are two paths from 0 to 3: 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]]
Explanation: Multiple paths exist from node 0 to node 4

Example 3:

Input: graph = [[1],[]]
Output: [[0,1]]
Explanation: Simple path from 0 to 1

Solution Approaches

Approach 1: DFS with Backtracking (Optimal)

Algorithm Explanation: Use depth-first search with backtracking to explore all possible paths from source to target. Since the graph is a DAG, we don’t need to worry about cycles.

Implementation:

Python:

def all_paths_source_target(graph):
    """
    Find all paths from source to target using DFS with backtracking
    Time: O(2^N * N) where N is number of nodes
    Space: O(2^N * N) for storing all paths
    """
    target = len(graph) - 1
    all_paths = []
    
    def dfs(node, path):
        # Base case: reached target
        if node == target:
            all_paths.append(path[:])  # Copy current path
            return
        
        # Explore all neighbors
        for neighbor in graph[node]:
            path.append(neighbor)
            dfs(neighbor, path)
            path.pop()  # Backtrack
    
    # Start DFS from node 0
    dfs(0, [0])
    return all_paths

def all_paths_source_target_optimized(graph):
    """
    Optimized version that builds path during recursion
    Time: O(2^N * N)
    Space: O(2^N * N)
    """
    target = len(graph) - 1
    
    def dfs(node):
        # Base case: reached target
        if node == target:
            return [[target]]
        
        paths = []
        for neighbor in graph[node]:
            # Get all paths from neighbor to target
            neighbor_paths = dfs(neighbor)
            # Prepend current node to each path
            for path in neighbor_paths:
                paths.append([node] + path)
        
        return paths
    
    return dfs(0)

def all_paths_iterative(graph):
    """
    Iterative solution using stack
    Time: O(2^N * N)
    Space: O(2^N * N)
    """
    target = len(graph) - 1
    all_paths = []
    
    # Stack contains (current_node, current_path)
    stack = [(0, [0])]
    
    while stack:
        node, path = stack.pop()
        
        if node == target:
            all_paths.append(path)
            continue
        
        for neighbor in graph[node]:
            stack.append((neighbor, path + [neighbor]))
    
    return all_paths

Java:

class Solution {
    /**
     * Find all paths from source to target using DFS with backtracking
     * Time: O(2^N * N)
     * Space: O(2^N * N)
     */
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        path.add(0);
        
        dfs(graph, 0, graph.length - 1, path, result);
        return result;
    }
    
    private void dfs(int[][] graph, int node, int target, 
                     List<Integer> path, List<List<Integer>> result) {
        if (node == target) {
            result.add(new ArrayList<>(path));
            return;
        }
        
        for (int neighbor : graph[node]) {
            path.add(neighbor);
            dfs(graph, neighbor, target, path, result);
            path.remove(path.size() - 1); // Backtrack
        }
    }
    
    /**
     * Alternative approach that builds paths during recursion
     */
    public List<List<Integer>> allPathsSourceTargetRecursive(int[][] graph) {
        return dfsRecursive(graph, 0, graph.length - 1);
    }
    
    private List<List<Integer>> dfsRecursive(int[][] graph, int node, int target) {
        List<List<Integer>> paths = new ArrayList<>();
        
        if (node == target) {
            List<Integer> path = new ArrayList<>();
            path.add(target);
            paths.add(path);
            return paths;
        }
        
        for (int neighbor : graph[node]) {
            List<List<Integer>> neighborPaths = dfsRecursive(graph, neighbor, target);
            for (List<Integer> path : neighborPaths) {
                List<Integer> newPath = new ArrayList<>();
                newPath.add(node);
                newPath.addAll(path);
                paths.add(newPath);
            }
        }
        
        return paths;
    }
    
    /**
     * Iterative solution using BFS approach
     */
    public List<List<Integer>> allPathsSourceTargetIterative(int[][] graph) {
        List<List<Integer>> result = new ArrayList<>();
        Queue<List<Integer>> queue = new LinkedList<>();
        
        List<Integer> initialPath = new ArrayList<>();
        initialPath.add(0);
        queue.offer(initialPath);
        
        while (!queue.isEmpty()) {
            List<Integer> currentPath = queue.poll();
            int currentNode = currentPath.get(currentPath.size() - 1);
            
            if (currentNode == graph.length - 1) {
                result.add(currentPath);
                continue;
            }
            
            for (int neighbor : graph[currentNode]) {
                List<Integer> newPath = new ArrayList<>(currentPath);
                newPath.add(neighbor);
                queue.offer(newPath);
            }
        }
        
        return result;
    }
}

Go:

// allPathsSourceTarget - Find all paths using DFS with backtracking
// Time: O(2^N * N)
// Space: O(2^N * N)
func allPathsSourceTarget(graph [][]int) [][]int {
    target := len(graph) - 1
    var result [][]int
    path := []int{0}
    
    var dfs func(int)
    dfs = func(node int) {
        if node == target {
            // Make a copy of current path
            pathCopy := make([]int, len(path))
            copy(pathCopy, path)
            result = append(result, pathCopy)
            return
        }
        
        for _, neighbor := range graph[node] {
            path = append(path, neighbor)
            dfs(neighbor)
            path = path[:len(path)-1] // Backtrack
        }
    }
    
    dfs(0)
    return result
}

// allPathsSourceTargetRecursive - Recursive approach building paths
func allPathsSourceTargetRecursive(graph [][]int) [][]int {
    target := len(graph) - 1
    
    var dfs func(int) [][]int
    dfs = func(node int) [][]int {
        if node == target {
            return [][]int{{target}}
        }
        
        var paths [][]int
        for _, neighbor := range graph[node] {
            neighborPaths := dfs(neighbor)
            for _, path := range neighborPaths {
                newPath := append([]int{node}, path...)
                paths = append(paths, newPath)
            }
        }
        
        return paths
    }
    
    return dfs(0)
}

// allPathsSourceTargetIterative - Iterative solution using queue
func allPathsSourceTargetIterative(graph [][]int) [][]int {
    target := len(graph) - 1
    var result [][]int
    
    // Queue of paths
    queue := [][]int{{0}}
    
    for len(queue) > 0 {
        currentPath := queue[0]
        queue = queue[1:]
        
        currentNode := currentPath[len(currentPath)-1]
        
        if currentNode == target {
            result = append(result, currentPath)
            continue
        }
        
        for _, neighbor := range graph[currentNode] {
            newPath := make([]int, len(currentPath)+1)
            copy(newPath, currentPath)
            newPath[len(currentPath)] = neighbor
            queue = append(queue, newPath)
        }
    }
    
    return result
}

// allPathsSourceTargetOptimized - Memory-optimized version
func allPathsSourceTargetOptimized(graph [][]int) [][]int {
    target := len(graph) - 1
    var result [][]int
    
    var dfs func(int, []int)
    dfs = func(node int, path []int) {
        if node == target {
            pathCopy := make([]int, len(path))
            copy(pathCopy, path)
            result = append(result, pathCopy)
            return
        }
        
        for _, neighbor := range graph[node] {
            dfs(neighbor, append(path, neighbor))
        }
    }
    
    dfs(0, []int{0})
    return result
}

JavaScript:

/**
 * Find all paths from source to target using DFS with backtracking
 * Time: O(2^N * N)
 * Space: O(2^N * N)
 */
function allPathsSourceTarget(graph) {
    const target = graph.length - 1;
    const result = [];
    
    function dfs(node, path) {
        if (node === target) {
            result.push([...path]); // Copy current path
            return;
        }
        
        for (const neighbor of graph[node]) {
            path.push(neighbor);
            dfs(neighbor, path);
            path.pop(); // Backtrack
        }
    }
    
    dfs(0, [0]);
    return result;
}

/**
 * Recursive approach that builds paths during recursion
 */
function allPathsSourceTargetRecursive(graph) {
    const target = graph.length - 1;
    
    function dfs(node) {
        if (node === target) {
            return [[target]];
        }
        
        const paths = [];
        for (const neighbor of graph[node]) {
            const neighborPaths = dfs(neighbor);
            for (const path of neighborPaths) {
                paths.push([node, ...path]);
            }
        }
        
        return paths;
    }
    
    return dfs(0);
}

/**
 * Iterative solution using BFS approach
 */
function allPathsSourceTargetIterative(graph) {
    const target = graph.length - 1;
    const result = [];
    const queue = [[0]]; // Queue of paths
    
    while (queue.length > 0) {
        const currentPath = queue.shift();
        const currentNode = currentPath[currentPath.length - 1];
        
        if (currentNode === target) {
            result.push(currentPath);
            continue;
        }
        
        for (const neighbor of graph[currentNode]) {
            queue.push([...currentPath, neighbor]);
        }
    }
    
    return result;
}

// ES6 version with modern syntax
const allPathsSourceTargetES6 = (graph) => {
    const target = graph.length - 1;
    const result = [];
    
    const dfs = (node, path = [0]) => {
        if (node === target) {
            result.push([...path]);
            return;
        }
        
        graph[node].forEach(neighbor => {
            path.push(neighbor);
            dfs(neighbor, path);
            path.pop();
        });
    };
    
    dfs(0);
    return result;
};

// Functional approach using reduce
const allPathsSourceTargetFunctional = (graph) => {
    const target = graph.length - 1;
    
    const dfs = (node) => {
        if (node === target) return [[target]];
        
        return graph[node].reduce((paths, neighbor) => {
            const neighborPaths = dfs(neighbor);
            return paths.concat(
                neighborPaths.map(path => [node, ...path])
            );
        }, []);
    };
    
    return dfs(0);
};

C#:

public class Solution {
    /// <summary>
    /// Find all paths from source to target using DFS with backtracking
    /// Time: O(2^N * N)
    /// Space: O(2^N * N)
    /// </summary>
    public IList<IList<int>> AllPathsSourceTarget(int[][] graph) {
        var result = new List<IList<int>>();
        var path = new List<int> { 0 };
        
        Dfs(graph, 0, graph.Length - 1, path, result);
        return result;
    }
    
    private void Dfs(int[][] graph, int node, int target, 
                     List<int> path, IList<IList<int>> result) {
        if (node == target) {
            result.Add(new List<int>(path));
            return;
        }
        
        foreach (int neighbor in graph[node]) {
            path.Add(neighbor);
            Dfs(graph, neighbor, target, path, result);
            path.RemoveAt(path.Count - 1); // Backtrack
        }
    }
    
    /// <summary>
    /// Alternative recursive approach
    /// </summary>
    public IList<IList<int>> AllPathsSourceTargetRecursive(int[][] graph) {
        return DfsRecursive(graph, 0, graph.Length - 1);
    }
    
    private IList<IList<int>> DfsRecursive(int[][] graph, int node, int target) {
        var paths = new List<IList<int>>();
        
        if (node == target) {
            paths.Add(new List<int> { target });
            return paths;
        }
        
        foreach (int neighbor in graph[node]) {
            var neighborPaths = DfsRecursive(graph, neighbor, target);
            foreach (var path in neighborPaths) {
                var newPath = new List<int> { node };
                newPath.AddRange(path);
                paths.Add(newPath);
            }
        }
        
        return paths;
    }
    
    /// <summary>
    /// LINQ-enhanced version with functional approach
    /// </summary>
    public IList<IList<int>> AllPathsSourceTargetLinq(int[][] graph) {
        int target = graph.Length - 1;
        
        IList<IList<int>> DfsLinq(int node) {
            if (node == target) {
                return new List<IList<int>> { new List<int> { target } };
            }
            
            return graph[node]
                .SelectMany(neighbor => DfsLinq(neighbor))
                .Select(path => new List<int> { node }.Concat(path).ToList())
                .Cast<IList<int>>()
                .ToList();
        }
        
        return DfsLinq(0);
    }
    
    /// <summary>
    /// Iterative solution using Queue (BFS-style)
    /// </summary>
    public IList<IList<int>> AllPathsSourceTargetIterative(int[][] graph) {
        int target = graph.Length - 1;
        var result = new List<IList<int>>();
        var queue = new Queue<List<int>>();
        
        queue.Enqueue(new List<int> { 0 });
        
        while (queue.Count > 0) {
            var currentPath = queue.Dequeue();
            int currentNode = currentPath[currentPath.Count - 1];
            
            if (currentNode == target) {
                result.Add(currentPath);
                continue;
            }
            
            foreach (int neighbor in graph[currentNode]) {
                var newPath = new List<int>(currentPath) { neighbor };
                queue.Enqueue(newPath);
            }
        }
        
        return result;
    }
}

Complexity Analysis:

Time Complexity: O(2^N * N) where N is the number of nodes
- In worst case, we might visit all possible paths
- Each path can have up to N nodes, so copying takes O(N) time
Space Complexity: O(2^N * N) for storing all possible paths

Trade-offs:

DFS with backtracking: Memory efficient during traversal, clean implementation
Recursive building: More functional style, builds paths naturally
Iterative BFS: No recursion depth limits, easy to understand
All approaches have same complexity due to problem nature

Approach 2: Memoization (Dynamic Programming)

Algorithm Explanation: Cache intermediate results to avoid recomputing paths from the same node.

Implementation:

Python:

def all_paths_source_target_memo(graph):
    """
    Memoized version to cache paths from each node
    Time: O(2^N * N) - same as basic, but faster in practice
    Space: O(2^N * N)
    """
    target = len(graph) - 1
    memo = {}
    
    def dfs(node):
        if node in memo:
            return memo[node]
        
        if node == target:
            memo[node] = [[target]]
            return memo[node]
        
        paths = []
        for neighbor in graph[node]:
            neighbor_paths = dfs(neighbor)
            for path in neighbor_paths:
                paths.append([node] + path)
        
        memo[node] = paths
        return paths
    
    return dfs(0)

# Using functools.lru_cache decorator
from functools import lru_cache

def all_paths_source_target_lru(graph):
    """
    Using Python's LRU cache decorator
    Time: O(2^N * N)
    Space: O(2^N * N)
    """
    target = len(graph) - 1
    graph_tuple = tuple(tuple(neighbors) for neighbors in graph)
    
    @lru_cache(maxsize=None)
    def dfs(node):
        if node == target:
            return [[target]]
        
        paths = []
        for neighbor in graph_tuple[node]:
            neighbor_paths = dfs(neighbor)
            for path in neighbor_paths:
                paths.append([node] + path)
        
        return paths
    
    return dfs(0)

Java:

class Solution {
    /**
     * Memoized version using HashMap
     * Time: O(2^N * N)
     * Space: O(2^N * N)
     */
    public List<List<Integer>> allPathsSourceTargetMemo(int[][] graph) {
        Map<Integer, List<List<Integer>>> memo = new HashMap<>();
        return dfsWithMemo(graph, 0, graph.length - 1, memo);
    }
    
    private List<List<Integer>> dfsWithMemo(int[][] graph, int node, int target,
                                           Map<Integer, List<List<Integer>>> memo) {
        if (memo.containsKey(node)) {
            return memo.get(node);
        }
        
        List<List<Integer>> paths = new ArrayList<>();
        
        if (node == target) {
            List<Integer> path = new ArrayList<>();
            path.add(target);
            paths.add(path);
            memo.put(node, paths);
            return paths;
        }
        
        for (int neighbor : graph[node]) {
            List<List<Integer>> neighborPaths = dfsWithMemo(graph, neighbor, target, memo);
            for (List<Integer> path : neighborPaths) {
                List<Integer> newPath = new ArrayList<>();
                newPath.add(node);
                newPath.addAll(path);
                paths.add(newPath);
            }
        }
        
        memo.put(node, paths);
        return paths;
    }
}

Complexity Analysis:

Time Complexity: O(2^N * N) - Same asymptotic complexity but faster in practice
Space Complexity: O(2^N * N) - Additional space for memoization

Trade-offs:

Better performance when nodes are revisited frequently
Additional memory overhead for caching
More complex implementation
Same worst-case complexity as basic approach

Key Insights

DAG property: No cycles means we can use simple DFS without visited tracking
Exponential paths: In worst case, there can be 2^N possible paths
Backtracking: Essential for exploring all paths while maintaining correct state
Path copying: Must copy paths when adding to result to avoid reference issues
Memory vs Time: Trade-off between memory usage and computation time

Edge Cases

Direct connection: Source directly connected to target → Single path
No path: Source not connected to target → Empty result
Multiple components: Disconnected graph → Some nodes unreachable
Linear path: Only one path exists → Single path in result
Complete graph: Multiple paths between every pair → Many paths
Single node paths: Path from node to itself → Trivial case

How Solutions Handle Edge Cases:

Direct connection: DFS finds immediate path
No path: DFS returns empty list naturally
Linear path: DFS follows unique path
Multiple paths: DFS explores all branches
All cases handled by basic DFS structure

Test Cases

def test_all_paths_source_target():
    # Example 1: Basic case
    graph1 = [[1,2],[3],[3],[]]
    result1 = all_paths_source_target(graph1)
    expected1 = [[0,1,3],[0,2,3]]
    assert sorted(result1) == sorted(expected1)
    
    # Example 2: Multiple paths
    graph2 = [[4,3,1],[3,2,4],[3],[4],[]]
    result2 = all_paths_source_target(graph2)
    assert len(result2) == 5
    
    # Example 3: Linear path
    graph3 = [[1],[2],[3],[]]
    result3 = all_paths_source_target(graph3)
    assert result3 == [[0,1,2,3]]
    
    # Example 4: Direct connection
    graph4 = [[1],[]]
    result4 = all_paths_source_target(graph4)
    assert result4 == [[0,1]]
    
    # Example 5: No path to target
    graph5 = [[1],[2],[]]
    result5 = all_paths_source_target(graph5)
    assert result5 == []
    
    # Example 6: Complex branching
    graph6 = [[1,2,3],[4],[4],[4],[]]
    result6 = all_paths_source_target(graph6)
    expected6 = [[0,1,4],[0,2,4],[0,3,4]]
    assert sorted(result6) == sorted(expected6)
    
    print("All tests passed!")

test_all_paths_source_target()

Follow-up Questions

Shortest path only: How would you modify to find only the shortest paths?
Path with constraints: What if some edges have weights or costs?
Cycle detection: How would you handle graphs with cycles?
Memory optimization: How could you reduce memory usage for large graphs?
Parallel processing: How would you parallelize the path finding?

Common Mistakes

Not copying paths: Storing references instead of path copies
- Problem: All result paths point to same mutable list
- Solution: Create new list copies when storing results
Forgetting to backtrack: Not removing nodes from path after recursive calls
- Problem: Path accumulates incorrect nodes
- Solution: Always pop after recursive DFS call
Visited array usage: Using visited tracking in DAG
- Problem: Prevents finding all valid paths
- Solution: Don’t use visited array for this problem
Base case errors: Incorrect handling of target node
- Problem: Missing paths or infinite recursion
- Solution: Proper base case when node equals target

Interview Tips

Clarify constraints: Confirm graph is DAG and ask about size limits
Start simple: Begin with basic DFS approach before optimizations
Explain complexity: Discuss why exponential time is unavoidable
Consider memory: Mention memory usage of storing all paths
Test edge cases: Walk through examples with different graph structures

Concept Explanations

Backtracking Pattern: This problem demonstrates classic backtracking where we explore all possibilities by making choices, recursing, then undoing choices to explore other options.

DAG Properties: Directed Acyclic Graphs allow simple traversal without cycle detection, making path enumeration straightforward compared to general directed graphs.

When to Apply: Use this approach for finding all possible routes, analyzing decision trees, solving maze problems, or any scenario requiring exhaustive path enumeration in directed graphs without cycles.