我具有以下功能,可生成给定数组的所有子集。
[这个想法很简单-我从一个包含一个空集(切片)的结果数组开始,对于输入数组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
是成员的set
切片。我用一些调试代码(请参见下文)对函数进行了一些修改,还发现了一种不会导致相同行为的解决方法(注释的代码)。
[我非常怀疑这是由引用传递而不是被复制而引起的(我将newSets
的元素附加到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})
}
问题在这里:
append(newSets, append(set, n))
问题不在于它是一个嵌套的追加。问题是您假设append(set,n)
将返回一个新切片。并非总是如此。切片是数组上的视图,当您向切片中添加新元素时,如果添加未导致重新分配数组,则返回的切片与您传入的切片相同,并且len
字段递增。因此,当您遍历结果数组时,您将修改已经存在的元素,同时,再次添加它们,就像它们是不同的结果一样。
为解决,当您获得result
的元素时,创建一个新的切片,将result
的元素复制到其中,附加新元素,然后将新的切片添加到result
。
问题很简单:append
采用切片参数-[]T
对于某些类型[[T-当然还要加上要附加的元素,并返回[]T
结果。但是[]T
(如果非零)则由两部分组成:slice header指向某个后备数组并带有当前长度和容量,以及backing array。当append
执行其工作时,可以选择:
append
副本
h
包含[0]
。现在您呼叫append(h, 1)
。 append操作将重新使用后备数组,并将1
放入第二个元素,并返回一个包含h1
的新切片头[0, 1]
。现在,您将h
again
追加到2
之后,制作一个包含h2
的两元素切片[0, 2]
。但是这将重复使用与h1
重用的相同的后备数组,因此现在h1
也拥有[0, 2]
。要解决该问题而又不修改太多算法,您需要:append
的变体,或func setPlusInt(set []int, n int) []int {
return append(append([]int(nil), set...), n)
}
这使您可以替换现有代码的一行。
((我做了另一个小改动here,并添加了足够的内容以在Go Playground中提供一个可行的示例。]
((另一种解决方案是设置每个自己的片头,以不提供额外的容量,因此append
必须始终进行复制。我没有说明此方法。)