Solution: All Paths From Source to Target

Explore how to use depth-first search combined with backtracking to find all possible paths from the source to the target node in a directed acyclic graph. Understand how to track paths efficiently and avoid cycles, gaining skills to solve complex graph traversal problems typically asked in coding interviews.

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