# All Paths From Source to Target
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/all-paths-from-source-to-target)
Canonical: https://scaleengineer.com/dsa/problems/all-paths-from-source-to-target
**Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Graph
---
## Problem
Given a directed acyclic graph (**DAG**) of `n` nodes labeled from `0` to `n - 1`, find all possible paths from node `0` to node `n - 1` and return them in **any order**.

The graph is given as follows: `graph[i]` is a list of all nodes you can visit from node `i` (i.e., there is a directed edge from node `i` to node `graph[i][j]`).

**Example 1:**

![](https://assets.glich.co/dsa/all-paths-from-source-to-target/image0.jpg) 

**Input:** graph = [[1,2],[3],[3],[]]
**Output:** [[0,1,3],[0,2,3]]
**Explanation:** There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.

**Example 2:**

![](https://assets.glich.co/dsa/all-paths-from-source-to-target/image1.jpg) 

**Input:** graph = [[4,3,1],[3,2,4],[3],[4],[]]
**Output:** [[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

**Constraints:**

* `n == graph.length`
* `2 <= n <= 15`
* `0 <= graph[i][j] < n`
* `graph[i][j] != i` (i.e., there will be no self-loops).
* All the elements of `graph[i]` are **unique**.
* The input graph is **guaranteed** to be a **DAG**.

# Approaches
## Breadth-First Search (BFS) with Path Tracking
This approach uses a Breadth-First Search (BFS) traversal to find all paths. We start from the source node `0` and explore the graph level by level. A queue is used to keep track of the paths being explored. Each element in the queue is a list of nodes representing a path from the source to the current node.
**Time:** O(N * 2^N). Let `N` be the number of nodes. The number of paths can be exponential in the worst case, up to `2^(N-2)`. Let `P` be the total number of paths. The total work is proportional to the sum of the lengths of all paths, as each extension of a path involves creating a new copy. A loose upper bound is `O(N * 2^N)`. · **Space:** O(N * 2^N). The space is dominated by the queue, which can store a large number of paths simultaneously. In a graph with a high branching factor, the number of paths at a certain depth can be very large. The total space required for the queue can be proportional to the total number of paths multiplied by their average length.
**Pros:** Conceptually simple to understand as it explores level by level.; Finds the shortest paths (in terms of number of edges) first, although this is not a requirement of the problem.
**Cons:** High space complexity. Storing all partial paths in the queue can consume a lot of memory, especially for graphs with many paths.; Inefficient due to the creation of many new list objects for each path extension.
### Explanation
We initialize a queue and add the initial path, which contains only the source node `0`. We also initialize a list `result` to store the final paths to the target. The algorithm proceeds by dequeuing a path and checking if its last node is the target. If it is the target, the path is added to our `result` list. If it's not the target, we extend the path by visiting all neighbors of the last node. For each neighbor, a new path is created by appending the neighbor to the current path, and this new path is enqueued. This process continues until the queue is empty, by which time all possible paths will have been explored.

```java
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> allPaths = new ArrayList<>();
        int n = graph.length;
        if (n == 0) {
            return allPaths;
        }

        Queue<List<Integer>> queue = new LinkedList<>();
        List<Integer> initialPath = new ArrayList<>();
        initialPath.add(0);
        queue.add(initialPath);

        while (!queue.isEmpty()) {
            List<Integer> currentPath = queue.poll();
            int lastNode = currentPath.get(currentPath.size() - 1);

            if (lastNode == n - 1) {
                allPaths.add(new ArrayList<>(currentPath));
                continue;
            }

            for (int neighbor : graph[lastNode]) {
                List<Integer> newPath = new ArrayList<>(currentPath);
                newPath.add(neighbor);
                queue.add(newPath);
            }
        }

        return allPaths;
    }
}
```
### Algorithm
- Create a list of lists `allPaths` to store the final result.
- Create a queue `queue` to store paths. A `LinkedList` can be used for this.
- Create an initial path `path` containing just the source node `0`.
- Add `path` to the `queue`.
- While the `queue` is not empty:
  - Dequeue the current path, `currentPath`.
  - Get the last node of `currentPath`, let's call it `lastNode`.
  - If `lastNode` is the target node (`n-1`), add a copy of `currentPath` to `allPaths`.
  - Otherwise, for each `neighbor` of `lastNode` in the graph:
    - Create a new path `newPath` by copying `currentPath` and adding `neighbor`.
    - Enqueue `newPath`.
- Return `allPaths`.

## Depth-First Search (DFS) with Backtracking
This is a more space-efficient approach using recursion and backtracking. We perform a Depth-First Search (DFS) from the source node `0`. We maintain a single path as we traverse deeper into the graph. When we reach the target node `n-1`, we've found a valid path and add it to our results. We then backtrack to explore other possibilities.
**Time:** O(N * 2^N). Similar to BFS, the time complexity is proportional to the number of paths and their lengths. Let `P` be the number of paths from source to target. The algorithm traverses each path once. For each path found, a copy is made, which takes `O(N)` time in the worst case (path length up to `N`). The total time is the sum of the lengths of all paths. A loose upper bound is `O(N * 2^N)`. · **Space:** O(N). The space complexity is determined by the recursion depth and the size of the `currentPath` list. Since the graph is a DAG, the maximum recursion depth is `N`. The `currentPath` also stores at most `N` nodes. This does not include the space required for the output list `allPaths`. If we include the output, the space is `O(N * P)`, where `P` is the number of paths.
**Pros:** Very space-efficient in terms of auxiliary space (`O(N)`).; Elegant and natural recursive solution for path-finding problems.; Avoids creating numerous intermediate path lists by modifying a single list in place.
**Cons:** The time complexity is still exponential in the worst case, which is unavoidable as the number of paths can be exponential.
### Explanation
The core of this approach is a recursive helper function, `dfs(currentNode, currentPath)`. We start the traversal from the source node `0`. The `currentPath` list keeps track of the nodes in the path from the source to the `currentNode`. When the `currentNode` is the target (`n-1`), we have found a complete path, so we add a copy of `currentPath` to our list of results. If the `currentNode` is not the target, we iterate through its neighbors. For each neighbor, we add it to the path and make a recursive call to `dfs`. After the recursive call for a neighbor returns, we must "backtrack" by removing the neighbor from `currentPath`. This crucial step allows us to explore other paths from the `currentNode` correctly.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> allPaths = new ArrayList<>();
        List<Integer> currentPath = new ArrayList<>();
        int n = graph.length;
        
        currentPath.add(0); // Start path with the source node
        dfs(graph, 0, n - 1, currentPath, allPaths);
        
        return allPaths;
    }

    private void dfs(int[][] graph, int currentNode, int targetNode, List<Integer> currentPath, List<List<Integer>> allPaths) {
        if (currentNode == targetNode) {
            allPaths.add(new ArrayList<>(currentPath));
            return; // Found a path, no need to explore further from target
        }

        // Explore neighbors
        for (int neighbor : graph[currentNode]) {
            // Add neighbor to path
            currentPath.add(neighbor);
            // Recurse
            dfs(graph, neighbor, targetNode, currentPath, allPaths);
            // Backtrack: remove neighbor from path
            currentPath.remove(currentPath.size() - 1);
        }
    }
}
```
### Algorithm
- Create a list of lists `allPaths` to store the final result.
- Create a list `currentPath` to store the path being explored during the traversal.
- Define a recursive function `dfs(graph, currentNode, targetNode, currentPath, allPaths)`.
- Add the source node `0` to `currentPath` to begin.
- Call the initial `dfs` function: `dfs(graph, 0, n-1, currentPath, allPaths)`.
- Inside the `dfs` function:
  - If `currentNode` equals `targetNode`, a complete path is found. Add a copy of `currentPath` to `allPaths` and return.
  - For each `neighbor` of `currentNode`:
    - Add `neighbor` to `currentPath`.
    - Recursively call `dfs(graph, neighbor, targetNode, currentPath, allPaths)`.
    - **Backtrack**: After the recursive call returns, remove `neighbor` from `currentPath` to explore other branches.
- Return `allPaths`.

# Solutions
### Java

```java
class Solution {
public
  List<List<Integer>> allPathsSourceTarget(int[][] graph) {
    int n = graph.length;
    Queue<List<Integer>> queue = new ArrayDeque<>();
    queue.offer(Arrays.asList(0));
    List<List<Integer>> ans = new ArrayList<>();
    while (!queue.isEmpty()) {
      List<Integer> path = queue.poll();
      int u = path.get(path.size() - 1);
      if (u == n - 1) {
        ans.add(path);
        continue;
      }
      for (int v : graph[u]) {
        List<Integer> next = new ArrayList<>(path);
        next.add(v);
        queue.offer(next);
      }
    }
    return ans;
  }
}

```

### JavaScript

```javascript
/** * @param {number[][]} graph * @return {number[][]} */ var allPathsSourceTarget = function ( graph ) { const ans = []; const t = [ 0 ]; const dfs = t => { const cur = t [ t . length - 1 ]; if ( cur == graph . length - 1 ) { ans . push ([... t ]); return ; } for ( const v of graph [ cur ]) { t . push ( v ); dfs ( t ); t . pop (); } }; dfs ( t ); return ans ; };
```

### CPP

```cpp
class Solution {
public:
  vector<vector<int>> graph;
  vector<vector<int>> ans;
  vector<vector<int>> allPathsSourceTarget(vector<vector<int>> &graph) {
    this->graph = graph;
    vector<int> path;
    path.push_back(0);
    dfs(0, path);
    return ans;
  }
  void dfs(int i, vector<int> path) {
    if (i == graph.size() - 1) {
      ans.push_back(path);
      return;
    }
    for (int j : graph[i]) {
      path.push_back(j);
      dfs(j, path);
      path.pop_back();
    }
  }
};

```

### Python

```python
class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]: n = len(graph) q = deque([[0]]) ans = [] while q: path = q . popleft() u = path[- 1] if u == n - 1: ans . append(path) continue for v in graph[u]: q . append(path + [v]) return ans

```