DFS/BFS part 2

797. All Paths From Source to Target

All Paths From Source to Target - LeetCode

My solution is below

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        self.res = []
        N = len(graph)
        def dfs(node, i):
            open_list = [(node,[[i]])]
            if node==N-1:self.res += [[i]]
            while open_list:
                node, path= open_list.pop()
                for nxt_node in graph[node]:
                    new_path = [p+[nxt_node] for p in path]
                    if nxt_node == N-1:
                        self.res += new_path
                        continue
                    open_list.append((nxt_node, new_path))
        dfs(0, 0)
        return self.res

Above solution is a standard DFS solution.

It can be written more concisely as below:

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        def dfs(cur, path):
            if cur == len(graph) - 1: res.append(path)
            else:
                for i in graph[cur]: dfs(i, path + [i])
        res = []
        dfs(0, [0])
        return res