DSA sheet · Graphs · Path enumeration (DFS + backtracking)

All Paths From Source to Target

Until now we only had to reach nodes. Here we must list every route from node 0 to the last node, so we have to remember the path we're walking. The teacher first solves it with BFS, where the queue holds whole paths. Then she uses DFS with one shared path list, which needs the most important new idea on this page: backtracking, which means add, recurse, remove. She also compares the space used by both. Backtracking comes back in subsets, permutations, N-Queens, word search and many more.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Graph basics this page needs (directed graphs, DAGs, paths)
• Part A · BFS: a queue of paths
• Part B · DFS with backtracking (the teacher's code)
• Part C · DFS without backtracking: pass a copy
• Part D · Revision page

Part 0 · Graph basics this page needs

Nodes, edges, directed and weighted

A graph is a set of nodes joined by edges. An undirected edge (a)—(b) can be walked both ways. A directed edge (a)→(b) is one-way: from a you can go to b, but not back. A weighted edge carries a number like a cost. This problem is directed and unweighted.

DAG: Directed Acyclic Graph

Acyclic means "no cycle": if you follow the arrows, you can never come back to a node you already passed. A DAG is a directed graph with no cycles. It matters a lot here, as we'll see: no cycle means no infinite walk, even without a visited array.

(0)→(1)
 ↓    ↓
(2)→(3)

(0)→(1)
 ↑    ↓
 └───(2)

Reading the input: an adjacency list is given directly

The input graph is already an adjacency list: graph[i] is the list of nodes you can go to from i (the children of i). Other problems give an edge list, which we'd convert like this:

n = 4
edges = [[0, 1], [0, 2], [1, 3], [2, 3]]     # u → v
graph = [[] for _ in range(n)]
for u, v in edges:
    graph[u].append(v)                       # one way only
print(graph)                                 # [[1, 2], [3], [3], []]

For an undirected graph you'd also do graph[v].append(u). An adjacency matrix would be an n × n grid of 0/1 where M[u][v] = 1 means an edge u → v.

Visited, components, BFS and DFS: a quick recap

In earlier problems (Provinces, Islands) we kept a visited array so each node was entered once. That was right there because we only cared about reaching nodes, not about the route. BFS uses a queue and spreads level by level. DFS uses recursion and dives deep first. Both appear on this page, but each needs a twist, because here the thing we store is a path, not a single node.

What is a path?

A path is a list of nodes where each consecutive pair is joined by an edge in the right direction, e.g. [0, 1, 3] uses 0→1 and 1→3. Two paths are different if their node lists differ, even if they share some nodes.

Part A · BFS: a queue of paths

LeetCode 797

1The question in simple words

You get a DAG with n nodes labelled 0 to n−1, given as an adjacency list. Return every path that starts at node 0 and ends at node n−1, following the arrows. You can return the paths in any order: for the example below, [[0,1,3],[0,2,3]] and [[0,2,3],[0,1,3]] are both accepted.

(0)→(1)
 ↓    ↓
(2)→(3)

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

0→4   0→3   0→1
1→3   1→2   1→4
2→3   3→4

paths: [0,4] [0,3,4] [0,1,3,4]
       [0,1,2,3,4] [0,1,4]

2What the constraints tell us

• 2 ≤ n ≤ 15 → very few nodes. The teacher's first reaction: with so few nodes we can afford to try every route. Even storing many full paths is fine.
• The graph is guaranteed to be a DAG → following arrows can never loop back. So we don't need a visited array to stop infinite loops.
• graph[i] has no self-loops (i never lists itself) and no repeated children → every child gives a genuinely different route.
• Start is always 0, target is always len(graph) - 1.

3Intuition: carry the whole route, not just the node

In normal BFS, the queue holds nodes. But if we only remember "I'm at node 3", we've forgotten how we got there, and the answer needs the route. So we make the queue hold whole paths. Think of many travellers starting at 0, each one carrying a notebook with the cities visited so far. At every fork the traveller splits into copies, one per road, and each copy writes its own next city. Whoever reaches the target hands their notebook to us.

4Building the logic from Example 1

Step 1: start

Every path starts at 0, so the queue starts with the path [0].

Step 2: pop a path, find where it ends, extend it to each child

Pop [0]. Its last node is 0, the node we're "standing on". The children of 0 are 1 and 2. For each child, make a new path = old path + child: [0,1] and [0,2]. Push both.

Step 3: keep going

Pop [0,1]. The last node is 1, and its child is 3 → push [0,1,3]. Pop [0,2]. The last node is 2, and its child is 3 → push [0,2,3].

Step 4: recognise a finished path

Pop [0,1,3]. Its last node is 3, which equals len(graph) - 1, so this is a complete valid path. Add it to the result. The same happens for [0,2,3]. The queue becomes empty, so we're done.

5Approach steps

1. target = len(graph) - 1, result = [], queue = deque([[0]]).
2. While the queue isn't empty: pop a path, node = path[-1].
3. If node == target: add the path to the result, then continue.
4. Else, for each child of node: push path + [child] (a new list).
5. Return the result.

6Code (Python)

from collections import deque

class Solution:
    def allPathsSourceTarget(self, graph):
        target = len(graph) - 1
        result = []
        queue = deque()
        queue.append([0])                        # the first path: just the source
        while queue:
            path = queue.popleft()
            node = path[-1]                      # where this path currently ends
            if node == target:
                result.append(path)              # complete route
                continue
            for child in graph[node]:
                queue.append(path + [child])     # a NEW list per child
        return result

7Code line by line

8Dry run on Example 1

9Complexity & remember

• Space: the teacher's main complaint about BFS. Here only 2 paths sat in the queue together, but if there were 100 routes, 100 full paths could be waiting at once. Worse, paths that share a beginning store that beginning again and again: [0,1,2,…,8,9] and [0,1,2,…,8,11] each keep their own copy of 0…8. So BFS takes about O(P · n) space, where P = number of paths and n = number of nodes.
• Time: we build every path once, copying up to n nodes each time → also about O(P · n) (see the note in Part B about how big P can get).
• The teacher's verdict: BFS works here only because n ≤ 15. For big inputs, avoid it for space reasons. She still recommends that you code the BFS version yourself as practice.

Part B · DFS with backtracking (the teacher's code)

1The question

Same as Part A: list every path 0 → n−1.

2Constraints

Same. n ≤ 15 means the recursion is at most 15 calls deep, which is no problem for Python.

3Intuition: one notebook, written in pencil

Now there's only one traveller with one notebook. Walk forward along one road and write the city in the notebook. At the target, photocopy the notebook page and file the copy in the result. Then walk back one step and erase the last city, so the notebook again shows where you really are, and try the next road from there.

Writing before you go, and erasing after you come back, is backtracking. Because we erase, one list is enough for every route.

4Building the logic step by step

Step 1: the start

Make result = [] and path = [0]. Node 0 is in the path from the beginning, because every route starts there. Call dfs(0).

Step 2: the base case: when is a path complete?

Inside dfs(node), first ask: is node == len(graph) - 1? If yes, the current path holds a full valid route. Save it and return, since there's no point going further. At node 0 this check fails (0 isn't the target), so we move on to the children.

Step 3: try every child: add, recurse, remove

For each child of the current node:

1. add: path.append(child). The notebook now shows the route up to the child.
2. recurse: dfs(child). Since this is DFS, the child becomes the new "parent", and we explore everything below it before doing anything else here.
3. remove: path.pop(). When that call returns, erase the child, so the path is back to what it was before step 1, and the next child starts from a clean state.

Step 4: the base case returns without removing. Is that a leak?

When dfs(3) saves and returns, it doesn't pop 3. That's fine, because it wasn't the one that added 3. Its caller added 3 just before calling, and its caller pops 3 right after the call. Each "add" is paired with exactly one "remove" in the same loop iteration.

5Approach steps

1. result = [], path = [0], call dfs(0), return result.
2. dfs(node): if node == len(graph) - 1 → append a copy of path to result, return.
3. For each child in graph[node]: path.append(child) → dfs(child) → path.pop().

6Code (Python)

class Solution:
    def allPathsSourceTarget(self, graph):
        result = []
        path = [0]                               # every route starts at 0
        self.dfs(0, graph, path, result)
        return result

    def dfs(self, node, graph, path, result):
        if node == len(graph) - 1:               # reached the target
            result.append(list(path))            # save a COPY
            return
        for child in graph[node]:                # graph[node], not graph.get(node)
            path.append(child)                   # 1. add
            self.dfs(child, graph, path, result) # 2. recurse
            path.pop()                           # 3. remove (backtrack)

The teacher's first run failed because she wrote graph.get(node) on a plain array. She fixed it by indexing with brackets, graph[node].

7Code line by line

8Dry run with the call stack (Example 1)

(0)→(1)
 ↓    ↓
(2)→(3)        graph = [[1,2],[3],[3],[]], target = 3

Look at the path column: it grows on the way down and shrinks on the way back up, mirroring the call stack exactly. That's the sign that backtracking is done right: when the stack is back to dfs(0), the path is back to [0].

            dfs(0) [0]
           /          \
   +1 dfs(1)[0,1]   +2 dfs(2)[0,2]
         |                 |
  +3 dfs(3)[0,1,3]   +3 dfs(3)[0,2,3]
       SAVE              SAVE

9Complexity & remember

• Extra space O(n) (not counting the answer). That's the teacher's main point: there is only one path list, and it is never longer than the longest route, at most n nodes. Her picture: 100 nodes where one route goes 0, 1, 3, 4, …, 99 through almost everything, so the path can hold about n nodes. The recursion stack is also at most n deep → O(n) + O(n) = O(n). BFS kept many paths alive at once → O(P · n). That's why DFS + backtracking wins on space.
• Time: the teacher says O(n) because "each node is reached". See the doubt below: that's not right for this problem.

Part C · DFS without backtracking: pass a copy

The teacher shows one more way, and why she didn't choose it.

1–2Question & constraints

Same as before.

3Intuition

Instead of one notebook that we write and erase, give each recursive call its own fresh notebook: path + [child]. Nobody shares, so nobody needs to erase.

4Why no removal is needed here

Her explanation: if the child is added inside the call's arguments rather than on its own line, then only the next call sees the longer path. In the current loop the variable path is still, say, [0,1]. When the call returns there's nothing to undo, because our own list was never touched.

5–6Steps and code

1. dfs(node, path): if node is the target → save path, return.
2. For each child → dfs(child, path + [child]). No append, no pop.

class Solution:
    def allPathsSourceTarget(self, graph):
        result = []
        target = len(graph) - 1

        def dfs(node, path):
            if node == target:
                result.append(path)              # this list is never changed again
                return
            for child in graph[node]:
                dfs(child, path + [child])       # a new list for the next call

        dfs(0, [0])
        return result

7Line by line (only what's new)

8Dry run (short)

dfs(0,[0]) → dfs(1,[0,1]) → dfs(3,[0,1,3]) saves → back in dfs(0), whose path is still [0] → dfs(2,[0,2]) → dfs(3,[0,2,3]) saves. Result: [[0,1,3],[0,2,3]] ✓. Three lists [0], [0,1], [0,1,3] existed at the deepest moment, where Part B had just one.

9Complexity

Time is the same, O(2ⁿ · n) worst case. Extra space: the lists alive along the current branch hold 1 + 2 + … + n items = O(n²), compared with O(n) for backtracking. That's a small difference at n = 15, but it's the habit the teacher wants us to build.

Part D · Revision page

s = Solution()
print(sorted(s.allPathsSourceTarget([[1, 2], [3], [3], []])))
# [[0, 1, 3], [0, 2, 3]]
print(sorted(s.allPathsSourceTarget([[4, 3, 1], [3, 2, 4], [3], [4], []])))
# [[0, 1, 2, 3, 4], [0, 1, 3, 4], [0, 1, 4], [0, 3, 4], [0, 4]]
print(s.allPathsSourceTarget([[1], []]))          # [[0, 1]]
print(s.allPathsSourceTarget([[], []]))           # []
complete = [[j for j in range(i + 1, 6)] for i in range(6)]
print(len(s.allPathsSourceTarget(complete)))      # 16

Based on this video: All Paths From Source to Target | Graph