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

问题出在 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])