797. All Paths From Source to Target - cocoder39/coco39_LC GitHub Wiki

797. All Paths From Source to Target

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

Time complexity: suppose originally there exists one path between start node and end node. One insight is that the number of paths can double every time we add a new node to graph. So in total there are 1+2+4+...+ 2*(N-2) = O(2^N) paths. For each path, there can be N nodes. So total time complexity is O(2^N * N)