go - 在 Golang 中生成 powerset 的代码给出了错误的结果

Question

Golang 中生成幂集的下一个代码在输入 {"A", "B", "C", "D", "E"} 时产生错误结果。我看到 [A B C E E] 作为最后生成的集合。

package main

import (
    "fmt"
)

func main() {
    for _, s := range PowerSet([]string{"A", "B", "C", "D", "E"}) {
        fmt.Println(s)  
    }   
}

func PowerSet(set []string) [][]string {
    var powerSet [][]string
    powerSet = append(powerSet, make([]string, 0))
    for _, element := range set {
        var moreSets [][]string
        for _, existingSet := range powerSet {
            newSet := append(existingSet, element)
            moreSets = append(moreSets, newSet)
        }
        powerSet = append(powerSet, moreSets...)
    }
    return powerSet
}

如何解决？如何在 Go 中地道地编写它？

Answer 1

你的程序的问题不是算法本身而是这一行:

newSet := append(existingSet, element)

您不应该附加并将其分配给不同的变量。

作为documentation状态(强调我的)，“append 内置函数将元素附加到 slice 的末尾。如果它有足够的容量，则重新 slice 目标以容纳新元素。如果没有，将分配一个新的底层数组。”。

因此，在某些情况下，newSet := append(existingSet, element) 实际上会修改 existingSet 本身，这会破坏您的逻辑。

如果您将其更改为创建一个新数组并附加到该数组，它会按您预期的那样工作。

newSet := make([]string, 0)
newSet = append(newSet, existingSet...) 
newSet = append(newSet, element)