All Paths From Source to Target

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.length
• 2 <= n <= 15
• 0 <= graph[i][j] < n
• graph[i][j] != i (i.e., there will be no self-loops).
• All the elements of graph[i] are unique.
• The input graph is guaranteed to be a DAG.

Approach: DFS Backtracking

Algorithm

1. Start DFS from node 0, appending each visited node to the current path
2. When the current node is n - 1, add a copy of the path to the result
3. Otherwise, recurse into every neighbor and then remove the node from the path (backtrack)
4. No visited set is needed because the graph is a DAG (no cycles)

Time & Space Complexity

• Time Complexity: O(2^n * n) - exponential paths in the worst case; each path costs O(n) to copy
• Space Complexity: O(n) - the recursion depth and the current path

Java Implementation

import java.util.ArrayList;
import java.util.List;

public class AllPathsFromSourceToTarget {

    /**
     * Return all paths from node 0 to node n - 1.
     * @param graph Adjacency list of the DAG
     * @return List of all paths
     */
    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);
        }
    }

    // Test method
    public static void main(String[] args) {
        AllPathsFromSourceToTarget ap = new AllPathsFromSourceToTarget();
        int[][] graph = {{1, 2}, {3}, {3}, {}};
        System.out.println("Input: graph = [[1,2],[3],[3],[]]");
        System.out.println("Output: " + ap.allPathsSourceTarget(graph));
        // Expected: [[0,1,3],[0,2,3]]
    }
}

Example Walkthrough

For graph = [[1,2],[3],[3],[]]:

1. Path starts at [0]
2. Visit neighbor 1: path [0,1]; from 1 visit 3 -> [0,1,3], node 3 is the target -> record
3. Backtrack to [0]; visit neighbor 2: path [0,2]; from 2 visit 3 -> [0,2,3] -> record

Result: [[0,1,3],[0,2,3]].

Key Points

1. DAG Property: No cycles, so a visited set is unnecessary; backtracking alone avoids repeats
2. Deep Copy: A new list is added because the path list is mutated during backtracking
3. Terminal Condition: The target is the node with index n - 1
4. Any Order: The problem accepts paths in any order
5. Small Bound: With n <= 15, the exponential worst case remains acceptable