797 All Paths From Source to Target

Intuition

Code

Python3

def allPathsSourceTarget(self, G: List[List[int]]) -> List[List[int]]:
 
    n = len(G)
    result = []
 
    def dfs(node, cur_path):
        if node == n - 1:
            cur_path.append(node)
            result.append(cur_path.copy())
            return
 
        cur_path.append(node)
 
        for neighbor in G[node]:
            dfs(neighbor, cur_path.copy())
 
        cur_path.pop()
 
        return
 
    dfs(0, [])
 
    return result

Big O Analysis

• Runtime

  The runtime complexity here is $O(N!)$ since we backtracking and checking all possible paths - where N is (E + V).

• Memory

  The memory usage is $O(N)$ where N is the max length of any of the paths.

— A

GitHub | Twitter