当元素数量超过5时，Go递归算法会生成虚假数据

Question

这是一个非常简单的程序，它枚举了元素列表的所有可能组合。问题是，当元素数量等于或大于 5 时，会生成虚假结果。

package main
import "fmt"

func Combination(choices []int) [][]int {
    result := [][]int{}
    if len(choices) == 0 {
        result = append(result, choices)
        return result
    } else {
        head := choices[0]
        tail := choices[1:]
        for _, combo := range Combination(tail) {
            result = append(result, combo)
            result = append(result, append(combo, head))
        }
    }
    return result
}

func main() {
    for idx, c := range Combination([]int{0, 1, 2, 3, 4}) {
        fmt.Println(idx, c)
    }
}

结果是

...
30 [4 3 2 0]
31 [4 3 2 0 0]

我已经花了很长时间但仍然一无所知。我怀疑这可能是切片的长度、盖子怪异，但我不确定。

谢谢

它应该生成所有可能的元素组合。

Answer 1

行

result = append(result, append(combo, head))

修改

combo

的原因是，它会导致组合被损坏的不良副作用。

由于 go 中的切片是引用类型，因此

append

可以就地修改其参数或返回其参数的副本以及附加条目

    a := []int{1, 2, 3}
    // return a copy of its argument
    a = append(a, 4)
    fmt.Println(a)
    // modify its argument in-place
    _ = append(a[:3], 5)
    fmt.Println(a)

所以正确的方法是：

package main

import "fmt"

func Combination(choices []int) [][]int {
    result := [][]int{}
    if len(choices) == 0 {
        result = append(result, []int{})
        return result
    } else {
        head := choices[0]
        tail := choices[1:]
        for _, combo := range Combination(tail) {
            result = append(result, combo)

            // Create a new combination
            newCombo := make([]int, len(combo))
            // Copy combo elemtnets to newCombo
            copy(newCombo, combo)
            // Adding head to a new slice
            newCombo = append(newCombo, head)

            result = append(result, newCombo)
        }
    }
    return result
}

func main() {
    for idx, c := range Combination([]int{0, 1, 2, 3, 4}) {
        fmt.Println(idx, c)
    }
}