What is the brute force approach and complexity for All Paths From Source to Target?

Queue whole paths; copy the path for every edge it extends with time complexity O(2ⁿ · n) and space complexity O(2ⁿ · n).

What is the optimal approach and complexity for All Paths From Source to Target?

Push and pop one path while walking; copy it when the target is reached with optimal time complexity O(2ⁿ · n) and space complexity O(n).

All Paths From Source to Target

Q: How do you identify the pattern for All Paths From Source to Target?

Look for key signals in the prompt: "directed graph, adjacency lists" indicates Edges have a direction, and a walk can only follow them forward. Each graph[i] is a list of choices.; "all paths from node 0 to node n − 1" indicates We must list every walk, so the search must try every choice. The answer is a list of paths.; "the graph has no cycles" indicates A walk can never repeat a node, so the search does not need a visited set.; "in any order" indicates The order of the answers does not matter, so the search order is free..

Medium·LeetCode #797 Pro OnlySlight Variation

LeetCode

Problem Statement

You are given a directed graph with n nodes, numbered 0 to n − 1. It is given as adjacency lists: graph[i] lists every node that node i has an edge to. The graph has no cycles, so it is a DAG (a directed acyclic graph).

Find every path from node 0 to node n − 1. A path follows the edges one by one. It ends when it reaches node n − 1.

Return all the paths. They can be in any order.

Input

graph, a list of n lists. graph[i] holds the nodes that node i points to.

Output

A list of every path from node 0 to node n − 1. Each path is a list of nodes that starts with 0 and ends with n − 1.

Example 1

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

Output: [[0,1,3],[0,2,3]]

Node 0 points to 1 and 2. Both of them point to 3, which is the target. That gives two paths.

Example 2

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]]

There are five paths. Node 3 is on three of them, so the same node appears in three answers.

Example 3

Input: graph = [[],[]]

Output: []

Node 0 has no edges, so no path reaches node 1.

Constraints

• n is the length of `graph`, with 2 ≤ n ≤ 15.
• Each number in `graph[i]` is a node from 0 to n − 1.
• No node has an edge to itself.
• The numbers inside each list `graph[i]` are unique.
• The graph has no cycles (it is a DAG).

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“directed graph, adjacency lists”

→ Edges have a direction, and a walk can only follow them forward. Each graph[i] is a list of choices.

“all paths from node 0 to node n − 1”

→ We must list every walk, so the search must try every choice. The answer is a list of paths.

“the graph has no cycles”

→ A walk can never repeat a node, so the search does not need a visited set.

“in any order”

→ The order of the answers does not matter, so the search order is free.

Approach Complexity Ladder

Brute Force — BFS with a whole path in every queue entryO(2ⁿ · n)O(2ⁿ · n)

Queue whole paths; copy the path for every edge it extends

Optimal — DFS with one shared path, no visited setO(2ⁿ · n)O(n)

Push and pop one path while walking; copy it when the target is reached

Brute Force Intuition

Start with the path [0] in a queue. Pop a path. If it ends at n − 1, it is an answer. Otherwise, for every edge out of its last node, copy the whole path and add the new node, and push each copy onto the queue. No list is ever shared, so every path is copied again and again.

Recognition rule for this sub-pattern:

DFS from a cell, mark it visited on the way in, unmark on the way out.

Remember this · Backtracking

Trigger

"All subsets / permutations / combinations", place items under rules (N-Queens, Sudoku), find a path in a grid.

Think

At each step, what are my choices, and how do I undo a choice?

Key question

What is my state, when is it complete, and when do I prune?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Backtracking translate into production architectures and low-level memory mechanics.

LLD Architecture