组合和在Go中
组合和在Go中
提问于 2017-04-01 15:59:18
/*
Given an array: [1,2] and a target: 4
Find the solution set that adds up to the target
in this case:
[1,1,1,1]
[1,1,2]
[2,2]
*/
import "sort"
func combinationSum(candidates []int, target int) [][]int {
sort.Ints(candidates)
return combine(0, target, []int{}, candidates)
}
func combine(sum int, target int, curComb []int, candidates []int) [][]int {
var tmp [][]int
var result [][]int
if sum == target {
fmt.Println(curComb)
return [][]int{curComb}
} else if sum < target {
for i,v := range candidates {
tmp = combine(sum+v, target, append(curComb, v), candidates[i:])
result = append(result,tmp...)
}
}
return result
}这是Leetcode中的一个问题，我使用递归来解决它。
在第18行，当和等于目标时，我打印每一种情况。产出如下：
[1,1,1,1]
[1,1,2]
[2,2]这就是我想要的答案！但是为什么最终的答案是(二维的)：
[[1,1,1,2],[1,1,2],[2,2]]预期答案是：[1,1,1,1,1,1,2,2,2]
请帮我找出密码中的错误。耽误您时间，实在对不起。
回答 1
Stack Overflow用户
回答已采纳
发布于 2017-04-01 19:53:35
这是因为切片的工作方式。切片对象是对底层数组的引用，以及切片的长度、数组中切片开始位置的指针以及片的容量。片的容量是从切片开始到数组末尾的元素数。当您附加到一个片段时，如果有新元素的可用容量，则将它添加到现有数组中。但是，如果没有足够的容量，append将分配一个新数组并复制元素。新数组的分配具有额外的容量，因此不需要对每个追加的数组进行分配。
在for循环中，当curComb是[1, 1, 1]时，其容量为4。在循环的连续迭代中，添加1和2，这两种方法都不会导致重新分配，因为数组中有足够的空间容纳新元素。当curComb是[1, 1, 1, 1]时，它会被放到结果列表中，但是在for循环的下一次迭代中，append将最后一个元素更改为2(请记住，它是相同的底层数组)，所以这就是在最后打印结果时所看到的。
解决方案是，当和等于目标时返回curComb的副本：
if sum == target {
fmt.Println(curComb)
tmpCurComb := make([]int, len(curComb))
copy(tmpCurComb, curComb)
return [][]int{tmpCurComb}这篇文章很好地解释了切片是如何工作的。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/43158984
复制相关文章
相似问题
腾讯云开发者
