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

Question

Next code in Golang to generate powerset produces wrong result on input {"A", "B", "C", "D", "E"}. I see [A B C E E] as the last generated set.

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
}

How to fix it? How to write it idiomatically in Go?

Answer 1

The problem with your program is not the algorithm itself but this line:

newSet := append(existingSet, element)

You should not append and assign to a different variable.

As the documentation states (emphasis mine), "The append built-in function appends elements to the end of a slice. If it has sufficient capacity, the destination is resliced to accommodate the new elements. If it does not, a new underlying array will be allocated.".

So, there might be cases where newSet := append(existingSet, element) will actually modify existingSet itself, which would break your logic.

If you change that to instead create a new array and append to that one, it works as you expect it.

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