如何避免 append 函数修改底层数组？

Question

我使用 Go 语言编写数组所有组合的算法，例如:

输入 {1, 2, 3}，

返回 {[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]}

算法代码如下，当输入数组元素少于 5 个时，能返回正确答案。但当使用 {1, 2, 3, 4, 5} 进行测试时，发现了一个我无法理解的问题。

package main

import "fmt"

func main() {
    res := subsets([]int{1, 2, 3, 4, 5})

    fmt.Println("---")
    for _, line := range res {
        fmt.Println(line)
    }

}

func subsets(nums []int) [][]int {
    res := [][]int{{}}
    n := len(nums)
    combine(0, n, &nums, []int{}, &res)

    return res
}

func combine(i, n int, nums *[]int, pre []int, res *[][]int) {
    for ; i < n; i++ {
        next := append(pre, (*nums)[i])
        fmt.Println(next)
        *res = append(*res, next)
        combine(i+1, n, nums, next, res)
    }
}

在第 25-27 行，我声明了一个 next []int 变量来保存即将加入到 res [][]int 数组里的值，然后将它打印出来。当算法之行结束后，我再检查 res 的值（9-11 行），却发现两次输出的结果不一致，输出如下：

[1]
[1 2]
[1 2 3]
[1 2 3 4]
[1 2 3 4 5]
[1 2 3 5]
[1 2 4]
[1 2 4 5]
[1 2 5]
[1 3]
[1 3 4]
[1 3 4 5]
[1 3 5]
[1 4]
[1 4 5]
[1 5]
[2]
[2 3]
[2 3 4]
[2 3 4 5]
[2 3 5]
[2 4]
[2 4 5]
[2 5]
[3]
[3 4]
[3 4 5]
[3 5]
[4]
[4 5]
[5]
---
[]
[1]
[1 2]
[1 2 3]
[1 2 3 5]
[1 2 3 4 5]
[1 2 3 5]
[1 2 4]
[1 2 4 5]
[1 2 5]
[1 3]
[1 3 4]
[1 3 4 5]
[1 3 5]
[1 4]
[1 4 5]
[1 5]
[2]
[2 3]
[2 3 4]
[2 3 4 5]
[2 3 5]
[2 4]
[2 4 5]
[2 5]
[3]
[3 4]
[3 4 5]
[3 5]
[4]
[4 5]
[5]

为了查看方便，我将两次结果对比：

可以看到在第 4 行，两次输出结果不一致。我调试的时候发现，在插入 res 的第 6 个元素前，执行 next := append(pre, (*nums)[i]) 语句时，突然修改了第 4 个元素的值。go 语言中数组不是指传递吗，并且这里的 next 我也是新声明的数组，另外当输入数组长度低于 5 时不会出现这种情况。这是为什么呢？

Answer 1

问题出在 append 函数上，如文档介绍的：

The append built-in function appends elements to the end of a slice. If it has sufficient capacity, the destination is resliced to accommodate the new elements. If it does not, a new underlying array will be allocated. Append returns the updated slice...

只有当切片的底层数组有的容量不足时，才会分配新的底层数组。也就是说，使用 append 可能会修改原来切片的值，例如：

package main

import "fmt"

func main() {
    a := []int{1,2,3,4,5}
    
    fmt.Println(cap(a))
    
    b := append(a, 6)
    c := append(b[:2], 100)
    
    fmt.Println(a)
    fmt.Println(b)
    fmt.Println(c)
    
}

输出：

5
[1 2 3 4 5]
[1 2 100 4 5 6]
[1 2 100]

切片 b 的值在运行 c := append(b[:2], 100) 语句时被修改了，而 a 的值不受影响。

但在上例中，之所以出现底层数组被修改是因为手动将 b 进行了切片（b[:2]），所以追加元素才不会超过原来的长度。那么在问题算法的代码里并没有切片的操作，一直在切片的末尾追加元素，为什么也会出现类似的问题呢？

append 的长度追加

这是因为 Go 语言在使用 append 追加元素时不是逐个增加底层数组的长度的，而是以一定倍数递增：

package main

import "fmt"

func main() {
    a := []int{}
    for i := 0; i < 10; i++ {
        a = append(a, i)
        fmt.Println(cap(a))
    }
}

输出：

1
2
4
4
8
8
8
8
16
16

可以看到，前两次 append 操作只增加了 1 个容量，而当第三次时追加了 2 个容量，底层数组的长度来到了 4。当这个数组被用满时，再次执行 append 时直接申请了一个长度为 8 的数组。而下一次申请新数组时更是达到了 16。也就是说，虽说上例执行了 10 次 append，但只有 5 个底层数组。具体地，第 1、2 个切片分别占用一个底层数组，第 3、4 个切片共用一个长度为 4 的底层数组，第 5、6、7、8 个切片共用一个长度为 8 的数组，9、10 共用一个。

具体地，结合到问题中那个算法，插入切片 [1,2,3] 时生成的底层数组长度为 4，那么插入 [1,2,3,4] 切片时实际上和 [1,2,3] 共用了一个数组。当递归回溯到 [1,2,3] 后面要追加元素 5 时，由于 [1,2,3] 底层数组长度为 4，不需要申请新的空间，所以直接在元数组上修改，导致了 [1,2,3,4] 也修改为 [1,2,3,5]。

解决方案

问题定位到了，解决方案就是强制为新切片分配一个新的底层数组：

next := make([]int, len(pre))
copy(next, pre)
next = append(next, (*nums)[i])