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 java导出word 动态填充数据
• ¥15 python SSH连接设备使用STD读配置卡死的问题
• ¥20 扑克的算牌公式及软件制作
• ¥20 如何通过云图中RPG去计算云图上不同位置的值？
• ¥15 请问不小心下载到了钓鱼软件怎么办？
• ¥15 求国博抢票 求国博抢票 有的私
• ¥50 swiftui @query 报错
• ¥50 怎么解决刷卡或扫码后，点击软件输入框，win10屏幕键盘不会自动弹出的问题
• ¥15 如何使用arcgispro的训练深度模型，发现water和nowater精度为0？（相关搜索：深度学习）
• ¥20 matlab作业不太懂呀有问题能给个代码吗