在Golang中使用回溯算法时如何正确复制数组？

在Golang中使用回溯算法时，正确复制数组是一个重要的问题。回溯算法通常需要在递归过程中对数组进行修改，但有时我们需要保存原始数组的状态以便回溯到上一步。在这种情况下，我们不能简单地将原始数组直接赋值给一个新变量，因为它们共享同一块内存空间，修改一个数组会影响到另一个数组。解决这个问题的方法是使用深拷贝，即创建一个新的数组并将原始数组的值依次复制到新数组中。在Golang中，可以使用copy()函数来完成这个操作，它会按字节级别复制数组的内容，确保新数组和原始数组完全独立。通过正确复制数组，我们可以在回溯算法中安全地操作数组，而不会影响到原始数据的状态。

问题内容

我有一个带有值 [1, 2, 3] 的简单数组，我想找到所有排列。我不明白为什么在循环中断程序之前移动“复制”部分代码。

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

   var res [][]int

   // DOESN'T WORK
   c, r := make([]int, len(curr)), make([]int, len(remains))
   copy(c, curr)
   copy(r, remains)

   for i := 0; i < len(remains); i++ {
      // WORKS
      //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
}

当复制位于循环之外时，结果如下： [[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]]

在第一个输出中，有两个带有 [3,3,3] 的数组，这是错误的

解决方法

你说我既不修改“c”或“r”也不附加到它们，这部分是正确的。

在循环的第一次迭代中， 切片 c 和 curr 指向不同的支持数组，所以这很好。

但是当你这么做的时候

curr = c

稍后，您实际上将两个切片分配为指向同一个支持数组。

这意味着在第二次迭代中，您的 append 可以修改 curr 和 curr （“可以”，因为调整大小会更改 curr 的支持数组）。

这就是导致您在上面看到的奇怪行为的原因。

go 中的切片有点棘手，所以当你知道你会改变并传递它们时，最好避免分配，而是坚持完全复制它们（就像在“works”情况下所做的那样）。

为了进一步阅读，这是一个很好的资源：https://go.dev/blog/slices-简介

以上是在Golang中使用回溯算法时如何正确复制数组？的详细内容。更多信息请关注PHP中文网其他相关文章！