My Go recursive function not working as expected due to slices

Question

I have written a function and I can't seem to find where the bug is:

The function change works like this:

An input of 15 (target value) with possible values of [1, 5, 10, 25, 100] should return [5, 10]. That's because to reach a target value of 15, the least amount of numbers to make up that target number is to have a 10 and 5

I use a caching mechanism, as it is a recursive function and remembers the values that have already been calculated.

func Change(coins []int, target int, resultsCache map[int][]int) ([]int, error) {
    if val, ok := resultsCache[target]; ok {
        return val, nil
    }
    if target == 0 {
        return make([]int, 0), nil
    }
    if target < 0 {
        return nil, errors.New("Target can't be less than zero")
    }

    var leastNumOfCoinChangeCombinations []int
    for _, coin := range coins {
        remainder := target - coin
        remainderCombination, _ := Change(coins, remainder, resultsCache)

        if remainderCombination != nil {
            combination := append(remainderCombination, coin)
            if leastNumOfCoinChangeCombinations == nil || len(combination) < len(leastNumOfCoinChangeCombinations) {
                leastNumOfCoinChangeCombinations = combination
            }
        }
    }
    if leastNumOfCoinChangeCombinations == nil {
        return nil, errors.New("Can't find changes from coin combinations")
    }
    sort.Ints(leastNumOfCoinChangeCombinations)
    resultsCache[target] = leastNumOfCoinChangeCombinations
    return leastNumOfCoinChangeCombinations, nil
}

The cache however have some abnormal behaviour, for example if I want to use the value of 12 in the cache later, instead of getting [2,5,5], I get [1 2 5] instead. Not sure where I went wrong. (but initially it was calculated and stored correctly, not sure how it got changed).

Here is a playground I used for troubleshooting:

https://play.golang.org/p/Rt8Sh_Ul-ge

Answer 1

You are encountering a fairly common, but sometimes difficult to spot, issue caused by the way slices work. Before reading further it's probably worth scanning the blog post Go Slices: usage and internals. The issue stems from the way append can reuse the slices underlying array as per this quote from the spec:

If the capacity of s is not large enough to fit the additional values, append allocates a new, sufficiently large underlying array that fits both the existing slice elements and the additional values. Otherwise, append re-uses the underlying array.

The below code provides a simple demonstration of what is occurring:

package main

import (
    "fmt"
    "sort"
)

func main() {
    x := []int{2, 3}
    x2 := append(x, 4)
    x3 := append(x2, 1)
    fmt.Println("x2 before sort", x2)
    sort.Ints(x3)
    fmt.Println("x2 after sort", x2)
    fmt.Println("x3", x3)
    fmt.Println("x2 cap", cap(x2))
}

The results are (playground):

x2 before sort [2 3 4]
x2 after sort [1 2 3]
x3 [1 2 3 4]
x2 cap 4

The result is probably not what you expected - why did x2 change when we sorted x3? The reason this happens is that the backing array for x2 has a capacity of 4 (length is 3) and when we append 1 the new slice x3 uses the same backing array (capacity 4, length 4). This only becomes an issue when we make a change to the portion of the backing array used by x2 and this happens when we call sort on x3.

So in your code you are adding a slice to the map but it's backing array is then being altered after that instance of Change returns (the append/sort ends up happening pretty much as in the example above).

There are a few ways you can fix this; removing the sort will do the trick but is probably not what you want. A better alternative is to take a copy of the slice; you can do this by replacing combination := append(remainderCombination, coin) with:

combination := make([]int, len(remainderCombination)+1)
copy(combination , remainderCombination)
combination[len(remainderCombination)] = coin

or the simpler (but perhaps not as easy to grasp - playground):

combination := append([]int{coin}, remainderCombination...)