Problem of The Day: All Paths From Source to Target

Problem Statement

leetcode problem link

Brute Force [Accepted]

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        res = []
        N = len(graph)

        def dfs(start, curr):
            if start == N - 1:
                res.append(curr[:])
                return
            for nei in graph[start]:
                dfs(nei, curr + [nei])


        dfs(0, [0])

        return res

Editorial

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:

        target = len(graph) - 1
        results = []

        def backtrack(curr_node, path):
            # if we reach the target, no need to explore further.
            if curr_node == target:
                results.append(list(path))
                return
            # explore the neighbor nodes one after another.
            for next_node in graph[curr_node]:
                path.append(next_node)
                backtrack(next_node, path)
                path.pop()
        # kick of the backtracking, starting from the source node (0).
        path = [0]
        backtrack(0, path)

        return results