# Pitfall to Avoid When Backtracking in Go With Slices

## Watch out for append() behavior

Oct 17, 2020 · 4 min read

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

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.

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

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

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.

Written by

## The Startup

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

Written by

## The Startup

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

## Has Javascript Killed PHP?

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