All Paths From Source to Target

Given a directed acyclic graph (DAG) of n nodes, find all paths from node 0 to node n-1 and return them in any order.

Example 1

Input: graph = [[1,2],[3],[3],[]] → Output: [[0,1,3],[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]]

Solution Approach

Use DFS/backtracking starting from node 0. At each node, explore all neighbors recursively. When we reach node n-1, add the current path to results. After recursion, remove the last node (backtrack).

Start DFS from node 0 with an initial path [0].
For each neighbor of the current node, add it to path and recurse.
When current node == n-1, add a copy of current path to results.
After recursion returns, remove the last node from path to backtrack.

Java

import java.util.*;

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        path.add(0);
        dfs(graph, 0, path, result);
        return result;
    }

    private void dfs(int[][] graph, int node, List<Integer> path, List<List<Integer>> result) {
        if (node == graph.length - 1) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int next : graph[node]) {
            path.add(next);
            dfs(graph, next, path, result);
            path.remove(path.size() - 1);
        }
    }
}

Time Complexity: O(2^N * N). Exponential paths in worst case
Space Complexity: O(N). Recursion stack depth