doumiyi7063 2019-02-25 04:30

# golang组合生成出错

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.

• 写回答

#### 1条回答默认 最新

• dse84825 2019-02-25 04:52
关注

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.

本回答被题主选为最佳回答 , 对您是否有帮助呢?
评论

#### 悬赏问题

• ¥15 opencv图像处理，需要四个处理结果图
• ¥20 centos linux 7.9安装php8.2.18不支持mysqli模块的问题
• ¥15 stata空间计量LM检验
• ¥15 NAO机器人说出txt文本内容
• ¥15 关于k8s node节点被释放后如何驱逐节点并添加新节点
• ¥15 subprocess.CalledProcessError: Command ‘[‘ninja‘, ‘-v‘]‘ returned non-zero exit status 1
• ¥15 for循环处理大量数据怎么优化
• ¥15 笔记本接显卡扩展坞重启报错
• ¥15 为什么这个指令报错啊，一直弄不懂为什么，想问问该怎么弄，决求解决，ubuntu刚入手