All Paths From Source to Target

lcpy gen -n 797   # by problem number
lcpy gen -s all_paths_source_target   # by problem name

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

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]]

class Solution:
    # Time: O(n + e) per path, O(2^n) total in the worst case
    # Space: O(n) recursion depth excluding the output
    def all_paths_source_target(self, graph: list[list[int]]) -> list[list[int]]:
        target = len(graph) - 1
        paths: list[list[int]] = []
        path = [0]

        def dfs(node: int) -> None:
            if node == target:
                paths.append(path[:])
                return
            for nxt in graph[node]:
                path.append(nxt)
                dfs(nxt)
                path.pop()

        dfs(0)
        return paths