Solution: All Paths From Source to Target

Explore how to solve the problem of finding all possible paths from the source node to the target node in a directed acyclic graph. Understand the use of depth-first search and backtracking to explore every route, track current paths, and backtrack to explore alternatives. This lesson teaches how to implement and analyze the solution's time and space complexities.

We'll cover the following...

Statement
Solution
- Time complexity
- Space complexity

Statement

You are given a directed acyclic graph (DAG) with $n$ nodes, labeled from $0$ to $n - 1$ . The graph is represented as an adjacency list, where graph[i] is a list of all nodes to which node i has a directed edge to.

Your task is to find all possible paths from node $0$ (the source) to node $n - 1$ (the target) and return them as a list of paths. Each path should be represented as a list of node indexes.

Note: You may return the answer in any order.

Constraints:

$2 \leq$ ...