go - slice 使用不当会导致意想不到的副作用

Question

我有以下函数可以生成给定数组的所有子集。

这个想法很简单——我从一个包含空集( slice )的结果数组开始，对于输入数组中的每个元素nums遍历所有先前生成的集合，添加 nums 的当前元素给他们并将生成的新集合添加回结果数组。没有什么特别有趣的。

func subsets(nums []int) [][]int {
  result := [][]int{{}}
  for _, n := range nums {
    newSets := [][]int{}
    for _, set := range result {
      newSets = append(newSets, append(set, n))
    }
    result = append(result, newSets...)
  }
  return result
}

问题是使用 append(newSets, append(set, n))破坏 result slice ，其中 set是成员(member)。我用一些调试代码(见下文)稍微修改了该函数，还找到了一个不会导致相同行为的解决方法(注释代码)。

我非常怀疑这是由通过引用传递而不是被复制的东西引起的(我将 newSets 的元素 append 到 result )。问题是我找不到它。 :( 我从不在循环中更改结果。我还为每个循环使用 newSets 的新实例。所以我不确定是什么原因造成的。请告知。:)

func subsets(nums []int) [][]int {

  result := [][]int{{}}
  for _, n := range nums {

    newSets := [][]int{}
    var before, after []int
    for _, set := range result {

      lastResultIdx := len(result)-1
      if lastResultIdx > 0 {
        before = make([]int, len(result[lastResultIdx]))
        copy(before, result[lastResultIdx])
      }

      //ns := []int{}
      //for _,v := range set {
      //  ns = append(ns, v)
      //}
      //ns = append(ns, n)
      //newSets = append(newSets, ns)

      newSets = append(newSets, append(set, n))

      if lastResultIdx > 0 {
        after = result[lastResultIdx]
        if before[len(before)-1]!=after[len(after)-1] {
          fmt.Println(n, "before", before, "after", after)
        }
      }
    }

    result = append(result, newSets...)
  }
  return result
}

func main() {
  subsets([]int{0, 1, 2, 3, 4})
}

Answer 1

问题在这里:

append(newSets, append(set, n))

问题不在于它是嵌套追加。问题是您假设 append(set,n)将返回一个新 slice 。情况并非总是如此。 slice 是数组的 View ，当您向 slice 添加新元素时，如果添加未导致数组重新分配，则返回的 slice 与您传入的 slice 相同，len字段递增。因此，当您浏览结果数组时，您正在修改已经存在的元素，同时再次添加它们，就好像它们是不同的结果一样。

要解决，当你得到 result 的一个元素时，创建一个新 slice ，复制result的元素向它添加新元素，然后将新 slice 添加到 result .