Pitfall to Avoid When Backtracking in Go With Slices

Cover image
4 min read
Go, Interview Question, Arrays

I found this cool graph-related programming exercise on LeetCode the other day:

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:

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:

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

Example 3:

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

Constraints:

n == graph.length
2 <= n <= 15
0 <= graph[i][j] < n
graph[i][j] != i (i.e., there will be no self-loops).
The input graph is guaranteed to be a DAG.
view raw question.md hosted with ❤ by GitHub
Example question
Figure 1: Graph for example 1 — From LeetCode

If you want to give it a try — take a break scrolling, and grab a piece of paper to scratch your algorithm. Spoiler after the graph 2 example.

Example question
Figure 2: Graph for example 2 — From LeetCode

Ok, there are many ways to implement a solution. In this article, I want to point out something specific about using backtracking to solve a graph problem using the Go programming language.

Backtracking is a good candidate whenever you can frame the problem as return all possible combinations verifying certain conditions.

My initial code for this approach was the following one:

func allPathsSourceTarget(graph [][]int) [][]int {
var paths [][]int
n := len(graph)
var backtrack func(int, []int)
backtrack = func(node int, curPath []int){
if node == n-1 {
paths = append(paths, append(curPath, node))
return
}
for _, child := range graph[node]{
backtrack(child, append(curPath, node))
}
}
backtrack(0, []int{})
return paths
}
view raw faultyV1.go hosted with ❤ by GitHub

We initialize paths, a slice of slice of int, in which we will store paths from node 0 to node n-1 as we encounter them.

We define a backtrack function taking a node and a curPath variable. We represent the current path curPath as a slice of integer we’ve been into so far.

Here we have the typical layout of a backtracking approach:

  1. We have a variable storing results,
  2. A recursive backtracking function browses a data structure checking whether :
    • the stop condition is met — here if we are at the last node, node == n-1
    • or exploring the data structure further from the current state — here in a BFS fashion.

But this code does not work — well it runs… but not returns the result you might expect.

Try with the input:

Input: graph = [[5,1],[5,3,7,2],[7,4,6,3,5],[4,7,5],[6,5,7],[7,6],[7],[]]

In fact, I made a big mistake in this first version, line 12 with backtrack(child, append(curPath, node)) The curPath might change for each child I iterate over.

For each child of graph[node] we must have the same state of the curPath before performing our recursive call. However, with the current implementation, the curPath slice might get modified with the append call.

Why might?

Because of how the append function works on slices in Go. The Go official documentation says:

The append built-in function appends elements to the end of a slice. If it has sufficient capacity, the destination is resliced to accommodate the new elements. If it does not, a new underlying array will be allocated. Append returns the updated slice. It is therefore necessary to store the result of append, often in the variable holding the slice itself

Indeed, a slice data structure in Go stores its value in an underlying array. If the array has some room available, we can add a new element without changing the underlying array. However, if the underlying array is full, we create a new one and copy the values from the old to the new underlying array.

For more context about slice internals, the Go blog has an excellent section on slices:

Slice internals

A slice is a descriptor of an array segment. It consists of a pointer to the array, the length of the segment, and its capacity (the maximum length of the segment).

Slice internals
Figure 3: The internal of a slice in go — From https://blog.golang.org/slices-intro

A variable s, created with the statement make([]byte, 5), is structured like this:

Slice and its internal array
Figure 4: Slice s and its underlying array — From https://blog.golang.org/slices-intro

So how can we solve this? To ensure each child of a node sees the same state of the current path, we must copy the curPath slice to ensure it remains similar for all children. That’s what the tmp slice achieves below.

func allPathsSourceTarget(graph [][]int) [][]int {
var paths [][]int
n := len(graph)
var backtrack func(int, []int)
backtrack = func(node int, curPath []int) {
if node == n-1 {
paths = append(paths, curPath)
return
}
lenCurPath := len(curPath)
for _, child := range graph[node] {
tmp := make([]int, lenCurPath, lenCurPath+1)
_ = copy(tmp, curPath)
tmp = append(tmp, child)
backtrack(child, tmp)
}
}
backtrack(0, []int{0})
return paths
}
view raw workingV2.go hosted with ❤ by GitHub

Et voilà! You now have a working backtracking implementation for this problem.

Key takeaway

The key to backtracking is to ensure that you start from the same state when you explore different options. Make sure to reverse any modification done on the shared data structure before recursing on the loop’s next item. Here, this meant having a clean copy of the current path at every recursive call to backtrack for the same graph[node].

Table of Contents