< 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.