Pitfall to Avoid When Backtracking in Go With Slices

Watch out for append() behavior

François Paupier
Oct 17, 2020 · 4 min read

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

A DAG
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.

A DAG
Graph for example 2 — From LeetCode

3...

2..

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:

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 :
    a. the stop condition is met — here if we are at the last node, node == n-1
    b. 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 Gofficial 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).

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

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

The Startup

Get smarter at building your thing. Join The Startup’s +800K followers.

François Paupier

Written by

Machine Learning Engineer — https://twitter.com/fpaupier

The Startup

Get smarter at building your thing. Follow to join The Startup’s +8 million monthly readers & +800K followers.

François Paupier

Written by

Machine Learning Engineer — https://twitter.com/fpaupier

The Startup

Get smarter at building your thing. Follow to join The Startup’s +8 million monthly readers & +800K followers.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store