797. All Paths From Source to Target

797. All Paths From Source to Target

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        
        dest = len(graph) - 1
        res = []
        
        def backtrack(curr, i):
            if i == dest:
                curr.append(i)
                res.append(curr.copy())
                curr.pop()
                return
            
            curr.append(i)
            for node in graph[i]:
                backtrack(curr, node)    
            curr.pop()
            
        backtrack([], 0)
        
        return res
            

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        target = len(graph) - 1
        res = []
        
        def backtrack(i, curr, visited):
            if len(curr) > 0 and curr[-1] == target:
                res.append(curr.copy())
                return
            
            for node in graph[i]:
                if node not in visited:
                    curr.append(node)
                    visited.add(node)
                    backtrack(node, curr, visited)
                    visited.remove(node)
                    curr.pop()
            
        
        backtrack(0, [0], set([0]))
        return res

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        target = len(graph) - 1
        res = []
        
        def backtrack(i, curr):
            if len(curr) > 0 and curr[-1] == target:
                res.append(curr.copy())
                return
            
            for node in graph[i]:
                curr.append(node)
                backtrack(node, curr)
                curr.pop()
            
        
        backtrack(0, [0])
        return res