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.