Leetcode 797. All Paths From Source to Target

Problem Explanation

You are given a directed, acyclic graph (DAG) made up of N nodes. The graph is described by an array where the index i represents a node and the elements of graph[i] represent its outgoing edges. You need to find all possible paths from node 0 to node N-1 and return the paths in any order. However, within each path, nodes should be in order.

Taking the example of [[1,2], [3], [3], []], the nodes and their respective edges are represented as follows:

1
2
30 -> 1, 2
41 -> 3
52 -> 3
63 -> 

This can be visually represented as:

1
2
30--->1
4|    |
5v    v
62--->3

In this case, there are two paths from node 0 to node N-1 (which is node 3 in this case): 0 -> 1 -> 3 and 0 -> 2 -> 3

Solution Approach

This problem can be solved using a depth-first search (DFS) algorithm. DFS is typically used for traversing or searching through a graph (or tree) and allows us to visit every possible node in the graph.

Our DFS function will start at node 0 (the source), from where it will explore all possible paths to node N-1 (the target). As it traverse through the graph, it will keep adding nodes to the current path. If it reaches the target node, the current path is added to the list of all paths. If it reaches a node with no further outgoing edges, it backtracks by removing the last node from the current path and continue exploring other possible paths.

More specifically, for each node u, we traverse each v in graph[u]. If v is our target (the node N-1), we add our path to the result. For non-target nodes, we add v to our path and recursively call our DFS function with v as our new node.

Here is a step-by-step walk through of the above approach using the given example:

1. Start at node 0. Path = [0]
2. Traverse to node 1 (which is the first element in graph[0]). Path = [0,1]
3. Traverse to node 3 (which is the only element in graph[1]). Since this is our target, we add the path [0,1,3] to our result and backtrack to node 1. Path = [0,1]
4. As there are no more elements in graph[1], we backtrack to node 0. Path = [0]
5. Traverse to node 2 (which is the next element in graph[0]). Path = [0,2]
6. Traverse to node 3 (which is the only element in graph[2]). Add the path [0,2,3] to our result. Now, as there are no more nodes to visit, our search ends.

Our final output is [[0,1,3],[0,2,3]] which represents all possible paths from node 0 to node 3.

Python Solution

1
2python
3class Solution:
4    def allPathsSourceTarget(self, graph):
5        def dfs(u, path):
6            if u == len(graph) - 1:  # if we reach target, add path to result
7                res.append(path)
8                return
9            for v in graph[u]:  # for each node, traverse all its neighbors
10                dfs(v, path + [v])  # recursively call dfs with new node 
11        
12        res = []
13        dfs(0, [0])  # start dfs from node 0
14        return res

Java Solution

1
2java
3import java.util.*;
4
5class Solution {
6    List<List<Integer>> res = new ArrayList<>();
7
8    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
9        dfs(graph, 0, new LinkedList<Integer>() {{
10            add(0);
11        }});
12        return res;
13    }
14
15    private void dfs(int[][] graph, int u, LinkedList<Integer> path) {
16        if (u == graph.length - 1) { // if we reach target, add path to result
17            res.add(new ArrayList<>(path));
18            return;
19        }
20        for (int v : graph[u]) {  // for each node, traverse all its neighbors
21            path.add(v);  // add the node to path
22            dfs(graph, v, path);  // recursively call dfs with new node
23            path.removeLast();  // backtrack if necessary
24        }
25    }
26}

JavaScript Solution

1
2javascript
3var allPathsSourceTarget = function(graph) {
4    let res = [];
5    dfs(graph, 0, [0]);
6    return res;
7
8    function dfs(graph, u, path) {
9        if(u === graph.length - 1) {
10            res.push(path);
11            return;
12        }
13        for(let v of graph[u]) {
14            dfs(graph, v, [...path, v]);
15        }
16    }
17};

C++ Solution

1
2cpp
3#include <vector>
4
5class Solution {
6    std::vector<std::vector<int>> res;
7
8public:
9    std::vector<std::vector<int>> allPathsSourceTarget(std::vector<std::vector<int>>& graph) {
10        std::vector<int> path{0};
11        dfs(graph, 0, path);
12        return res;
13    }
14
15    void dfs(std::vector<std::vector<int>>& graph, int u, std::vector<int>& path) {
16        if(u == graph.size()-1) {
17            res.push_back(path);
18            return;
19        }
20        for(auto &v: graph[u]) {
21            path.push_back(v);
22            dfs(graph, v, path);
23            path.pop_back();
24        }
25    }
26};

C# Solution

1
2csharp
3public class Solution {
4    List<IList<int>> result = new List<IList<int>>();
5    int target;
6    int[][] graph;
7
8    public IList<IList<int>> AllPathsSourceTarget(int[][] graph) {
9        target = graph.Length - 1;
10        this.graph = graph;
11        DFS(0, new List<int>(new int[]{ 0 }));
12        return result;
13    }
14    
15    public void DFS(int node, List<int> path) {
16        if(node == target)
17            result.Add(new List<int>(path));
18
19        foreach(int nei in graph[node]) {
20            path.Add(nei);
21            DFS(nei, path);
22            path.RemoveAt(path.Count - 1);
23        }
24    }
25}

In the python, java, javascript, c++ and c# code, both the BFS and DFS algorithm loops through each element of the graph and traverses it. If the target is reached, it is added to the result. The path is backtracked if necessary. The main difference between the codes is how the elements are represented and traversed in different languages.## Ruby Solution

1
2ruby
3def all_paths_source_target(graph)
4  res = []
5  dfs(graph, 0, [0], res)
6  return res
7end
8
9def dfs(graph, node, path, res)
10  if node == graph.length - 1
11    res << path.dup
12    return
13  end
14
15  graph[node].each do |nei|
16    path << nei
17    dfs(graph, nei, path, res)
18    path.pop
19  end
20end

The ruby code follows the same approach of BFS and DFS algorithm seen in the previous codes. In Ruby however, handling of collections like graphs and arrays is different and operations can be performed on them using different collection methods provided natively by Ruby.

Swift Solution

1
2swift
3class Solution {
4    func allPathsSourceTarget(_ graph: [[Int]]) -> [[Int]] {
5        var res = [[Int]]()
6        dfs(graph, 0, [0], &res)
7        return res
8    }
9
10    private func dfs(_ graph: [[Int]], _ node: Int, _ path: [Int], _ res: inout [[Int]]) {
11        if node == graph.count - 1 {
12            res.append(path)
13            return
14        }
15
16        for nei in graph[node] {
17            dfs(graph, nei, path + [nei], &res)
18        }
19    }
20}

In Swift, the Breadth-First-Search(BFS) and Depth-First-Search(DFS) algorithm is implemented similarly to Java, Python, and JavaScript. The path is backtracked if necessary. The graph traversal operations, adding elements to list and calling recursive function with new parameters are achieved in the same way.

Kotlin Solution

1
2kotlin
3class Solution {
4    fun allPathsSourceTarget(graph: Array<IntArray>) : List<List<Int>> {
5        val paths: MutableList<List<Int>> = mutableListOf()
6        val pathNodes: Stack<Int> = Stack()
7        pathNodes.push(0)
8        dfs(0, graph, pathNodes, paths)
9        return paths
10    }
11
12    private fun dfs(node: Int, graph: Array<IntArray>, pathNodes: Stack<Int>, paths: MutableList<List<Int>>) {
13        if (node == graph.size - 1) {
14            paths.add(pathNodes.toList())
15        } else {
16            for (nextNode in graph[node]) {
17                pathNodes.push(nextNode)
18                dfs(nextNode, graph, pathNodes, paths)
19                pathNodes.pop()
20            }
21        }
22    }
23}

Similar to the previous solutions, Kotlin uses DFS to navigate through the graph. The current node is pushed onto the stack and the function is recursively called again for that node. If the node is a target, the current path is added to the list of all paths. If the current node does not have any neighbors or if all its neighbors have been explored then we backtrack using pathNodes.pop().