使用 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

如果list有容量，那么它会被修改，因此你正在修改你的论点。而是制作列表的副本，然后将 nums[i] 附加到它。

见Go Slices: usage and internals

Answer 2

append 函数可能会也可能不会修改切片引用的基础数组。因此，您在使用追加时并没有创建一个全新的列表。我更改了 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)
}

Answer 3

行

helper(nums, i, target - nums[i], append(list, nums[i]), resultp, length)

可能无法按预期执行。它在循环内调用，您可能假设在每次迭代中 append 总是将新成员添加到现有切片中。如果有更复杂的行为你似乎不够关心：

如果新值适合切片的后备数组的当前容量，则将其添加到当前后备数组。分配给该切片的所有变量现在报告更新后的内容以及存在的新值。
如果该值不适合，则分配一个新数组。在这种情况下，如果还保留旧值，则对返回切片的进一步修改不会更改初始切片的内容。

我的印象是，您可能不会预料 append 返回的值与您传递给它的参数 list 之间存在 value/content 分歧。

描述了此行为 here（滚动到 "gotcha"）。

Answer 4

所以你可以通过添加一些打印输出来更好地看到行为：

https://play.golang.org/p/JPmqoAJE4S

重要的是，此时可以看到：

0694 helper [2 3 7] 1 1 [2 2 2 2 2 2 2 3] [[2 2 2 2 2 2 2 2 2]] 3
4425 calling down 1 6 [2 2 2 2 2 2] 3
8511 helper [2 3 7] 1 3 [2 2 2 2 2 2 3] [[2 2 2 2 2 2 2 2 2]] 3
8511 calling down 1 3 [2 2 2 2 2 2 3] 3
8162 helper [2 3 7] 1 0 [2 2 2 2 2 2 3 3] [[2 2 2 2 2 2 2 2 2]] 3
8162 solution [2 2 2 2 2 2 3 3] [[2 2 2 2 2 2 2 2 2] [2 2 2 2 2 2 3 3]]
1318 calling down 1 8 [2 2 2 2 2] 3
5089 helper [2 3 7] 1 5 [2 2 2 2 2 3] [[2 2 2 2 2 2 2 2 2] [2 2 2 2 2 3 3 3]] 3
5089 calling down 1 5 [2 2 2 2 2 3] 3
4728 helper [2 3 7] 1 2 [2 2 2 2 2 3 3] [[2 2 2 2 2 2 2 2 2] [2 2 2 2 2 3 3 3]] 3
1318 calling down 2 8 [2 2 2 2 2] 7
3274 helper [2 3 7] 2 1 [2 2 2 2 2 7] [[2 2 2 2 2 2 2 2 2] [2 2 2 2 2 7 3 3]] 3

这是操作顺序：

您使用 [2 2 2 2 2 2 3] 递归调用并附加 3。您发现这是一个有效的解决方案并将 [2 2 2 2 2 2 3 3] 添加到结果切片。
你 return 上升了几个级别，直到你回到 [2 2 2 2 2]（在添加第 6 个 2 之前）并开始尝试添加 3s。您使用 [2 2 2 2 2] 递归调用并追加 3。不幸的是，这会覆盖您现有的解决方案 [2 2 2 2 2 2 3 3]。由于它使用 相同的后备数组 ，您将 3 附加到该切片中的前 5 个项目，覆盖您之前添加到解决方案集中的切片中的第 6 个索引。您的第二个解决方案变为 [2 2 2 2 2 3 3 3]（注意第 6 个插槽中的 3）
您发现此解决方案集在几次迭代后（在 [2 2 2 2 2 3 3]）无法工作，因为剩余的目标 (2) 小于最后添加的数字 (3)，因此您 return up.
您在第 6 个槽中使用 7 重复此序列，再次覆盖基础数组索引。您的第二个解决方案变为 [2 2 2 2 2 7 3 3]，因为您仍然使用相同的底层数组。你发现这个解决方案也行不通，return起来。

在这一点之后，您 return 直到列表切片的长度大于 4（这是切片增长的时候，默认情况下它的大小增加一倍），这意味着您正在使用一个不同的（先前的）支持数组，这就是为什么进一步的迭代不会进一步改变现有的解决方案。幸运的是，none 剩余的解决方案以类似的方式发生碰撞。

此替代打印版本向您显示支持数组更改的位置（通过显示第一个条目的地址更改的位置）：https://play.golang.org/p/nrgtMyqwow。如您所见，当长度超过 2、4 和 8 时，它会发生变化，但是当您 return 向上时，您最终会恢复到不同的支持数组。

解决您的特定问题的最简单方法是在将列表切片添加到解决方案集之前复制它：

if target == 0 {
    sol := make([]int, len(list))
    copy(sol, list)
    *resultp = append(*resultp, sol)
    return
}

https://play.golang.org/p/3qTKoAumj0

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

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

Confused about the depth-first-search result when using Golang

go

depth-first-search