golang组合生成出错

Question

I'm dealing with a programming problem

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

and with input n = 5, k = 4, the output should be [[1,2,3,4],[1,2,3,5],[1,2,4,5],[1,3,4,5],[2,3,4,5]], the following is my golang solution

func combine(n int, k int) [][]int {
    result := [][]int{}
    comb := []int{}
    subcom(0, k, n, &comb, &result)
    return result
}

func subcom(s, k, n int, comb *[]int, result *[][]int) {
    if k > 0 {
        for i := s + 1; i <= n-k+1; i++ {
            c := append(*comb, i)
            subcom(i, k-1, n, &c, result)
        }
    } else {
        *result = append(*result, *comb)
    }
}

I think my solution is right, but it return [[1 2 3 5] [1 2 3 5] [1 2 4 5] [1 3 4 5] [2 3 4 5]].

After debugging, I found [1 2 3 4] was added to the result slice at the beginning, but later changed to [1 2 3 5], resulting in the repetition of two [1 2 3 5]s. But I can't figure out what's wrong here.

Answer 1

This is a common mistake when using append.

When your code runs c:=append(*comb,i), it tries to first use the allocated memory in the underlying array to add a new item and only create a new slice when it failed to do so. This is what changes the [1 2 3 4] to [1 2 3 5] - because they share the same underlying memory.

To fix this, copy when you want to append into result:

now := make([]int,len(*comb))
copy(now,*comb)
*result = append(*result,now)

Or use a shortcut of copying:

*result = append(*result, append([]int{},*comb...))

Update:

To understand what I mean by underlying memory, one should understandd the internal model of Go's slice.

In Go, a slice has a data structure called SliceHeader which is accessible through reflect package and is what being referred to when you use unsafe.Sizeof and taking address.

The SliceHeader taking cares of three elements: Len,Cap and a Ptr. The fisrt two is trivail: they are what len() and cap() is for. The last one is a uintptr that points to the memory of the data the slice is containing.

When you shallow-copy a slice, a new SliceHeader is created but with the same content, including Ptr. So the underlying memory is not copied, but shared.