golang组合生成出错

Question

我正在处理一个编程问题给定两个整数 n 和 k，返回 1 ... n 中 k 个数字的所有可能组合。输入 n = 5，k = 4，输出应为 [[1,2,3,4],[1,2,3,5],[1,2,4,5],[1,3 ,4,5],[2,3,4,5]],下面是我的golang方案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)    }}我认为我的解决方案是正确的，但它返回 [[1 2 3 5] [1 2 3 5] [1 2 4 5] [1 3 4 5] [2 3 4 5]]。调试后发现result slice一开始添加了[1 2 3 4]，后来改成了[1 2 3 5]，导致重复了两个[1 2 3 5]。但我不知道这里出了什么问题。

Answer 1

这是使用append.

当您的代码运行时c:=append(*comb,i)，它会尝试首先使用底层数组中分配的内存来添加一个新项，并且仅在失败时才创建一个新切片。这就是改变的原因[1 2 3 4]——[1 2 3 5]因为它们共享相同的底层内存。

要解决此问题，请在要附加到结果时复制：

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

或者使用复制的快捷方式：

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

更新：

要理解我所说的底层内存的意思，应该理解 Go 切片的内部模型。

在 Go 中，一个 slice 有一个数据结构，可以SliceHeader通过reflectpackage 访问它，它是你使用和获取地址时所引用的unsafe.Sizeof。

照顾SliceHeader三个要素：Len和Capa Ptr。前两个是微不足道的：它们是什么len()，cap()是为了什么。最后一个是uintptr指向切片包含的数据的内存。

当您浅拷贝一个切片时，SliceHeader会创建一个新的但内容相同的切片，包括Ptr. 所以底层内存不是复制的，而是共享的。