How to solve Leetcode 797. 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 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]]

Example 3

Input: graph = [[1],[]]
Output: [[0,1]]

Example 4

Input: graph = [[1,2,3],[2],[3],[]]
Output: [[0,1,2,3],[0,2,3],[0,3]]

Example 5

Input: graph = [[1,3],[2],[3],[]]
Output: [[0,1,2,3],[0,3]]

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: Depth-first search (DFS)

This problem is exactly the Depth-first search algorithm.

Code

#include <vector>
#include <iostream>
using namespace std;
void DFS(vector<vector<int>>& graph, vector<vector<int>>& paths, vector<int>& path) {
    for (auto& node : graph[path.back()]) {
        path.push_back(node);
        if (node == graph.size() - 1) {
            paths.push_back(path);
            path.pop_back();
        } else {
            DFS(graph, paths, path);
        }
    }
    path.pop_back();
}
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
    vector<vector<int>> paths;
    vector<int> path = {0};
    DFS(graph, paths, path);
    return paths;
}
void printPaths(vector<vector<int>>& paths) {
    cout << "[";
    for (auto& p : paths) {
        cout << "[";
        for (auto& node : p) {
            cout << node << ",";
        }
        cout << "],";
    }
    cout << "]\n";
}
int main() {
    vector<vector<int>> graph = {{1,2},{3},{3},{}};
    auto paths = allPathsSourceTarget(graph);
    printPaths(paths);
    graph = {{4,3,1},{3,2,4},{3},{4},{}};
    paths = allPathsSourceTarget(graph);
    printPaths(paths); 
}

Output:
[[0,1,3,],[0,2,3,],]
[[0,4,],[0,3,4,],[0,1,3,4,],[0,1,2,3,4,],[0,1,4,],]

Complexity

Runtime: O(N^2), where N = graph.length.
Extra space: O(N).

References

Get my FREE book "10 Classic Coding Challenges"

How to solve Leetcode 797. All Paths From Source to Target

Comments

More from this blog

Leetcode 59. How To Go Around A Square Matrix In Spiral Order

Leetcode 120. How To Find The Minimum Path From Top To Bottom Of A Triangle

How To Find The Longest Substring Without Repeating Characters

How To Find The Maximal Subarray Having Distinct Elements

Common Mistakes in Coding Interviews and How to Avoid Them

Problem statement

Example 1

Example 2

Example 3

Example 4

Example 5

Constraints

Solution: Depth-first search (DFS)

Code

Complexity

References

Command Palette

Comments

More from this blog

Problem statement

Example 1

Example 2

Example 3

Example 4

Example 5

Constraints

Solution: Depth-first search (DFS)

Code

Complexity

References