leetcode-DAG

797. All Paths From Source to Target.py

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        """
        
        Thought process:
            1. we use backtracking to generate all possible pathes from node 0 to node n-1
            
        Time complexity analysis:
            Except the starting and ending node, each node could be included in the path or not. In an exntrem case, there're goingt to 2^(n-1) pathes from node 0 to node n-1 .So, time complexity could roughly be 2 raise to power of n.
            
        T:(2^n)
        """
        n = len(graph)
        self.ans = []
        def backtrack(cur, path):
            if cur == n - 1: 
                # meet the target node
                self.ans.append(path)
            for nei in graph[cur]: 
                backtrack(nei, path + [nei])
                
        source_n, path = 0, [0]
        backtrack(source_n, path) 
        return self.ans