Medium

All Paths From Source to Target

LAB

Given a DAG adjacency list, return every path from node 0 to node n-1 in lexicographic order.

EXAMPLES

Example 1

Input
{
  "graph": [
    [
      1,
      2
    ],
    [
      3
    ],
    [
      3
    ],
    []
  ]
}

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

FUNCTION SHAPE

graph: intMatrix→intMatrix

SOLUTION NOTE

Honestly DP and dfs are very similar. For DAG's, I would argue they are identical. (if there are cycles in a graph, DP won't work…)

Just define the dp definition, the base case, and think about how to use the recursive call dfs(nbr) to create the current output.

Reveal reference solution +

pythonREFERENCE

# just dfs. since this is a DAG -> cache works!
def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
    @cache
    def dfs(i): # returns a list of all paths from i to n-1.
        if i == len(graph)-1:
            return [[i]]
        res = []
        for nbr in graph[i]:
            for nbr_path in dfs(nbr):
                res.append([i] + nbr_path)
        return res
    return dfs(0)

TimeO(2^n * n)

SpaceO(2^n * n)

Open on LeetCode ↗