< Back





797. All Paths From Source to Target

We're given a directed acyclic graph (DAG) and we're asked to find all paths from the source, 0, to
the target, n - 1, where n is the length of graph. For graph[i], where i is the node, we're provided
a list of node i's neighbors.

To solve this, we use DFS from the source node, 0, and we keep track of the path for each path being
traversed - similar to backtracking. When we reach the target node, we add the path to our answer.

The solution is as follows:


  class Solution:
      def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
          n, ans = len(graph), []

          stack = [(0, [])]

          while stack:
              node, path = stack.pop()
              path.append(node)

              if node == n - 1:
                  ans.append(path[:])

              for neighbor in graph[node]:
                  stack.append((neighbor, path[:]))

          return ans


_ Time Complexity:

  O(n * 2^n) - There could be, at most, 2^n paths from the source to the target node. For each path,
  there could be at most n nodes.

_ Space Complexity:

  O(n) - The stack could contain, at most, n nodes.