Solution: All Paths From Source to Target

Explore how to solve the problem of finding all paths from source to target in a directed acyclic graph using depth-first search combined with backtracking. Understand the recursive approach, path tracking, and backtracking techniques to ensure every valid path is discovered without redundancy. This lesson helps you apply graph traversal strategies to enumerate all possible routes, preparing you for complex coding interview challenges involving DAGs and combinatorial path exploration.

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