All Paths From Source to Target

Leetcode Problem 797: All Paths From Source to Target

Problem Summary

Given a directed acyclic graph (DAG) of n nodes labeled from 0 to n - 1, represented as an adjacency list where graph[i] contains all nodes reachable from node i by a single edge, find all possible paths from node 0 to node n - 1 and return them in any order. The graph has at most 15 nodes and is guaranteed to be a DAG.

Techniques

• Backtracking
• Depth-First Search
• Breadth-First Search
• Graph

Solution

function dfs(node: number, graph: number[][], path: number[], result: number[][]) {
    path.push(node)

    if (node === graph.length - 1) {
        result.push([...path])
    } else {
        for (const child of graph[node]) {
            dfs(child, graph, path, result)
        }
    }

    path.pop()
}

function allPathsSourceTarget(graph: number[][]): number[][] {
    const result: number[][] = []
    dfs(0, graph, [], result)
    return result
};