Go语言二维切片递归中append()修改原切片的问题排查

问题场景 #

在实现「候选数组元素可重复使用、找出和为目标值的所有组合」的递归逻辑时，直接将临时组合切片tmpComboappend到结果二维切片theList后，出现了异常：已经添加到theList里的组合[3 3 3 3 3 3]，后续被修改成了[3 3 3 3 3 2]。只有先复制tmpCombo的元素到新切片，再将新切片append到theList，才能避免这个问题。

同时产生疑惑：append(arr, ele)在普通循环里不会修改原切片，为什么递归里会出现这种情况？

问题根源 #

Go的切片是引用类型，它的底层结构包含三个部分：指向底层数组的指针、切片长度、切片容量。当你直接把tmpComboappend到theList时，theList里存储的是tmpCombo的引用（也就是底层数组的指针），而不是元素的副本。

在递归的回溯过程中，你会修改tmpCombo的元素（比如最后一位替换成其他候选值），这本质上是在修改共享的底层数组元素，所以之前已经存入theList的组合，因为指向同一个底层数组，会被同步修改。

而普通循环里没有后续修改原切片底层数组的操作，所以不会暴露这个引用共享的问题。

解决方案 #

每次要将临时组合存入结果切片前，先复制tmpCombo的所有元素到一个新切片，再把新切片append到theList：

// 复制tmpCombo到新切片
newCombo := make([]int, len(tmpCombo))
copy(newCombo, tmpCombo)
// 将新切片加入结果
theList = append(theList, newCombo)

这样theList里的每个组合都指向独立的底层数组，后续修改tmpCombo不会影响已经存入的结果。

内容的提问来源于stack exchange，提问作者TurtleTread