Problem 22.7 · Depth-First SearchMedium

All Paths From Source to Target

PatternGraph DFS and Flood Fill Backtracking

What it teaches: Path enumeration on a DAG with add / recurse / remove.

Practise it on judges as “All Paths From Source to Target”.

The problem

A DAG with n nodes is given as graph[i] = the nodes i points to. Return every path from node 0 to node n − 1, in any order.

Example 1

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

Constraints

2 ≤ n ≤ 15
The graph is acyclic

Pattern clues in the wording

→ "All paths"
→ DAG

These clues point to Graph DFS and Flood Fill: Go as deep as possible from a node, marking visited cells or nodes, to find connected regions.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        return new ArrayList<>();
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	graph = [[1,2],[3],[3],[]]	[[0,1,3],[0,2,3]]
2	graph = [[4,3,1],[3,2,4],[3],[4],[]]	[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

From slow to fast

Approaches

1. Backtracking DFS · O(2ⁿ × n) worst case

Backtracking DFS

Time O(2ⁿ × n) worst case Space O(n) besides the output

path.add(u); if u is the target, record a copy; else recurse on each successor; path.remove(last).

Approach 1

import java.util.*;

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> out = new ArrayList<>();
        dfs(graph, 0, new ArrayList<>(), out);
        return out;
    }

    private void dfs(int[][] g, int u, List<Integer> path, List<List<Integer>> out) {
        path.add(u);
        if (u == g.length - 1) out.add(new ArrayList<>(path));
        else for (int v : g[u]) dfs(g, v, path, out);
        path.remove(path.size() - 1);
    }
}

Verdict: Output-sensitive; can't do better in general.

Before you submit

Edge cases and common mistakes

Test these inputs

Direct edge 0 → n − 1
Many shared sub-paths

Mistakes people make

Adding path itself (all entries end up as the same empty list).

Interview

Follow-up questions

How do you count paths without listing them?

Command Palette

The problem

Approaches

Backtracking DFS

Edge cases and common mistakes

Follow-up questions