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

Question

I tried to solve the 'Combination Sum' on leetcode, and the result is wrong when using test case:

[7,3,2] 18

I used C++ with the same logic and passed, but when using Golang, my result is:

[[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]]

and the correct one should be

[[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]]

the code is shown below:

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)
    }
}

Can anyone tell me why the result is incorrect, I am just confused about the [2,2,2,2,2,7,3,3] in my answer, why the 7 is before the 3 since the array has been sorted? Or anyone can tell me what mistake I have made in my code

Answer 1

append function may or may not modify the underlying array that your slice refers to. So you are not creating a completely new list when using append. I changed helper to match your desired behavior.

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)
}