Golang回溯算法中数组复制的正确方式：循环外复制为何出错？

问题重现 #

有一个值为[1, 2, 3]的数组，想要生成其所有全排列，但发现将数组复制代码移到循环外时，程序输出错误结果：

[[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 3 3] [3 3 3]]

而将复制代码放在循环内时，结果正确：

[[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 1 2] [3 2 1]]

对应的代码如下：

func generatePermutations(curr, remains []int) [][]int {
   if len(remains) == 0 {
      return [][]int{curr}
   }

   var res [][]int

   // 放在循环外会出错
   c, r := make([]int, len(curr)), make([]int, len(remains))
   copy(c, curr)
   copy(r, remains)

   for i := 0; i < len(remains); i++ {
      // 放在循环内正常工作
      //c, r := make([]int, len(curr)), make([]int, len(remains))
      //copy(c, curr)
      //copy(r, remains)
      
      curr = append(curr, remains[i])
      res = append(res, generatePermutations(curr, append(append(remains[:i]), remains[i+1:]...))...)

      curr = c
      remains = r
   }

   return res
}

问题原因 #

核心在于Go语言中切片是引用类型——切片本身只是包含底层数组指针、长度、容量的结构体，问题出在循环外复制的r切片被意外修改：

1. 循环外复制的情况：

   • 只在循环开始前创建一次r，复制初始的remains值。此时r的底层数组是固定的，后续循环中remains被赋值为r，两者共享同一个底层数组。
   • 执行append(remains[:i], remains[i+1:]...)时，remains[:i]是基于r底层数组的切片（容量等于r的容量）。如果append的元素数量未超过该切片的容量，Go会直接在原底层数组上修改，覆盖原有元素。
   • 比如第一次循环处理i=0时，append(remains[:0], remains[1:]...)会把remains[1:]的元素写到r底层数组的起始位置，直接污染了r的内容。后续循环再把remains赋值为r时，拿到的已经是被修改后的错误数据，最终导致递归生成错误排列。

2. 循环内复制的情况：

   • 每次循环都会重新创建c和r，复制当前的curr和remains值。每次循环的r都是独立的新切片，拥有自己的底层数组。
   • 后续对remains的append操作只会修改当前循环内的临时切片，不会影响下一次循环使用的原始remains数据，因此递归过程中所有数据都是正确的。

总结 #

要避免这类引用类型的坑，需确保每次循环处理的是独立的数据副本。在这个场景下，必须把切片的复制操作放在循环内部，保证每次循环都基于原始的curr和remains生成新副本，避免底层数组被意外修改。

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