Go递归组合算法元素数≥5时生成错误数据求助

你的怀疑完全正确，问题根源就是Go切片的底层数组复用机制。

在递归循环里，你执行了两个操作：

1. result = append(result, combo) —— 把当前的combo切片直接加入结果集
2. result = append(result, append(combo, head)) —— 在combo基础上追加head后加入结果集

但Go的append函数在切片容量足够时，会直接复用原切片的底层数组。这就意味着，当你执行第二步的append(combo, head)时，如果combo的cap大于len，修改的是和第一步存入result的combo共享的底层数组，后续的递归操作会不断污染这些已经存入结果的切片，最终导致出现重复元素（比如你看到的[4 3 2 0 0]）。当元素数量≥5时，递归过程中生成的切片容量刚好触发了这个复用逻辑，才会暴露问题。

修复代码 #

解决办法很简单：每次追加head时，创建一个新的切片，避免复用原combo的底层数组。修改Combination函数中的循环部分即可：

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)
            // 创建新切片，先复制combo的所有元素，再追加head
            newCombo := append(append([]int{}, combo...), head)
            result = append(result, newCombo)
        }
    }
    return result
}

原理说明 #

append([]int{}, combo...)会创建一个全新的切片，其底层数组和原combo完全独立。之后再追加head，修改的是新切片的底层数组，不会影响已经存入result的combo切片。这样就能保证所有生成的组合都是独立且正确的。

运行修改后的代码，就能得到所有合法的元素组合，不会再出现重复元素的问题。

内容的提问来源于stack exchange，提问作者Jon Huang