797. 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.

Solution:

DFS

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();

        List<Integer> subResult = new ArrayList<Integer>();

        subResult.add(0);

        dfs(graph, 0, subResult, result);

        return result;
    }


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

        for (int next : graph[node]){
            subResult.add(next);
            dfs(graph, next, subResult, result);
            subResult.remove(subResult.size() - 1);
        }
    }
}

Time Complexity: $O(2^VV)$. Here, $V$ represents the number of vertices.
For a directed acyclic graph (DAG) with $V$ vertices, there could be at most $2^{V-1} - 1$ possible paths to go from the starting vertex to the target vertex. We need $O(V)$ time to build each such path.
Therefore, a loose upper bound on the time complexity would be $(2^{V-1} - 1)O(V) = O(2^vV) $.
Since we have overlap between the paths, the actual time spent on the traversal will be lower to some extent.
Space Complexity: $O(V)$. The recursion depth can be no more than $V$, and we need $O(V)$ space to store all the previously visited vertices while recursively traversing deeper with the current path. Please note that we don't count the space usage for the output, i.e., to store all the paths we obtained.

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        int n = graph.length;

        // SC: O(v + E)
        Map<Integer, List<Integer>> adj = new HashMap<>();
        for (int i = 0; i < n; i++){
            adj.put(i, new ArrayList<>());

        }

        for (int i = 0; i < n - 1; i++){
            int[] g = graph[i];
            for (int j = 0; j < g.length; j++){
                adj.get(i).add(g[j]);

            }
        }
        Set<Integer> visited = new HashSet<Integer>(); // SC: O(n)
        int start = 0;
        List<Integer> subResult = new ArrayList<>();
        subResult.add(start);
        dfs(n-1, start, adj, subResult, result, visited);

        return result;
    }

    public void dfs(int target, int cur, Map<Integer, List<Integer>> adj, List<Integer> subResult, List<List<Integer>> result,  Set<Integer> visited){

        if (cur == target){
            result.add(new ArrayList<>(subResult));
            return;
        }

        if (visited.contains(cur)){
            return;
        }

        visited.add(cur);



        for (int next : adj.get(cur)){ // 0, 1, 3 // 0,2,3
            subResult.add(next); // [0, 1]
            dfs(target, next, adj,subResult, result, visited);
            subResult.remove(subResult.size() - 1);
        }

        visited.remove(cur);


    }
}

/*
0: 1, 2
1: 3,
2: 3,
*/

// TC: O(2^n + E)
// SC: O(n*2^n + V + E)

BFS

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();

        Deque<List<Integer>> queue = new ArrayDeque<>();

        List<Integer> subResult = new ArrayList<Integer>();


        subResult.add(0);
        queue.offerLast(subResult);

        while(!queue.isEmpty()){ // 0 
            List<Integer> curSubResult = queue.poll();
            int curNode = curSubResult.get(curSubResult.size() - 1);
            for (int next : graph[curNode]){
                List<Integer> nextSubResult = new ArrayList<>(curSubResult);
                nextSubResult.add(next);
                if (next == graph.length - 1){
                    result.add(new ArrayList<Integer>(nextSubResult));
                }else{
                    queue.add(new ArrayList<Integer>(nextSubResult));
                }

            }

        }

        return result;
    }
}

Time Complexity: $O(2^VV)$. Here, $V$ represents the number of vertices.
For a graph with $V$ vertices, there could be at most $2^{V -1} -1$ possible paths to go from the starting vertex to the target vertex. We need $O(V)$ time to build each such path.
Therefore, a loose upper bound on the time complexity would be $(2^{V-1} - 1) O(V) = O(2^V V)$.
Since we have overlapping between the paths, the actual time spent on the traversal will be lower to some extent.
Space Complexity: $O(2^vV)$. The queue can contain $O(2^v)$ paths and each path will take $O(V)$ space. Therefore, the overall space complexity is $O(2^vV)$.