go - 使用 Golang 时对深度优先搜索结果感到困惑

Question

我试过leetcode上的'Combination Sum'，用test case的时候结果是错误的:

[7,3,2] 18

我用同样逻辑的C++也通过了，但是用Golang的时候，我的结果是:

[[2,2,2,2,2,2,2,2,2],[2,2,2,2,2,7,3,3],[2,2,2,2,3,7],[2,2,2,3,3,3,3],[2,2,7,7],[2,3,3,3,7],[3,3,3,3,3,3]]

正确的应该是

[[2,2,2,2,2,2,2,2,2],[2,2,2,2,2,2,3,3],[2,2,2,2,3,7],[2,2,2,3,3,3,3],[2,2,7,7],[2,3,3,3,7],[3,3,3,3,3,3]]

代码如下:

import "sort"
func combinationSum(candidates []int, target int) [][]int {
    result := make([][]int, 0, 0)
    resultp := &result
    sort.Ints(candidates)
    helper(candidates, 0, target, make([]int, 0, 0), resultp, len(candidates))
    return *resultp
}

func helper(nums []int, index int, target int, list []int, resultp *[][]int, length int) {
    if target == 0 {
        *resultp = append(*resultp, list)
        return
    }
    for i := index; i < length; i++ {
        if i != index && nums[i] == nums[i - 1] {
            continue
        }
        if (nums[i] > target) {
            break
        }
        helper(nums, i, target - nums[i], append(list, nums[i]), resultp, length)
    }
}

谁能告诉我为什么结果不正确，我只是对我的回答中的 [2,2,2,2,2,7,3,3] 感到困惑，为什么 7 在 3 之前，因为数组已排序？或者任何人都可以告诉我我在代码中犯了什么错误

Answer 1

append 函数可能会也可能不会修改 slice 引用的底层数组。因此，您在使用追加时并没有创建一个全新的列表。我更改了 helper 以匹配您想要的行为。

for i := index; i < length; i++ {
    if i != index && nums[i] == nums[i - 1] {
        continue
    }
    if nums[i] > target {
        break
    }
    var newList []int
    newList = append(newList, list...)
    newList = append(newList, nums[i])
    helper(nums, i, target - nums[i], newList, resultp, length)
}