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.
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:
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:
- We have a variable storing results,
- 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-1b. 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],,]
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.
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
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:
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).
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.
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