请教一个关于Go中的切片问题
采用回溯算法用Go解下面这道组合问题,过程中遇到一个问题!
给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。你可以按 任何顺序 返回答案。
采用典型的回溯算法。
var result [][]int var nums []int func combine(n int, k int) [][]int { result=[][]int{} nums=[]int{} backtracking(n, k, 1) return result } func backtracking(n, k, start int) { if len(nums) == k { // 符合条件的组合加入result result = append(result, nums) //fmt.Println(nums) //fmt.Printf("%v,%d,%p\n", result, i, result) return // 返回空 } for i := start; i <= n; i++ { nums = append(nums, i) backtracking(n, k, i+1) nums = nums[:len(nums)-1] } }
输出的结果却是:[[4 4] [4 4] [4 4] [4 4] [4 4] [4 4]]。
于是通过Println进行测试(代码中注释掉的),结果是[1 2] [1 3] [1 4] [2 3] [2 4] [3 4]
证明nums中保存的结果没有问题。
那么很有可能是result = append(result, nums)
的问题。于是输出result的值。结果却是:
[[1 2]],0xc000004078 [[1 3] [1 3]],0xc000078480 [[1 4] [1 4] [1 4]],0xc00005e060 [[2 3] [2 3] [2 3] [2 3]],0xc00005e060 [[2 4] [2 4] [2 4] [2 4] [2 4]],0xc00007e000 [[3 4] [3 4] [3 4] [3 4] [3 4] [3 4]],0xc00007e000
又看了下,而且nums和result地址并不一样, 想不明白为什么会输出这样的结果?
[1],0xc000012088 [1 2],0xc0000120d0 [[1 2]],0xc0000040d8 [1 3],0xc0000120d0 [[1 3] [1 3]],0xc000078480 [1 4],0xc0000120d0 [[1 4] [1 4] [1 4]],0xc00005e060 [2],0xc0000120d0 [2 3],0xc0000120d0 [[2 3] [2 3] [2 3] [2 3]],0xc00005e060 [2 4],0xc0000120d0 [[2 4] [2 4] [2 4] [2 4] [2 4]],0xc00007e000 [3],0xc0000120d0 [3 4],0xc0000120d0 [[3 4] [3 4] [3 4] [3 4] [3 4] [3 4]],0xc00007e000 [4],0xc0000120d0
而输出正确的结果只要,进行如下修改:
var result [][]int var nums []int func combine(n int, k int) [][]int { result=[][]int{} nums=[]int{} backtracking(n,k,1) return result } func backtracking(n, k, start int) { if len(nums)==k { temp:=make([]int,k) // 改成如下 copy(temp,nums) result=append(result,temp) //result=append(result,nums) return // 返回空 } for i:=start;i<=n;i++ { nums=append(nums,i) backtracking(n,k,i+1) nums=nums[:len(nums)-1] } }
结果输出正确结果[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
。
这是为什么呢?
也有想过可能是append之后存放符合条件组合切片的地址变了,本质上应该是一个深拷贝和浅拷贝混合作用的结果。但还是没能理清楚,不能说服自己。
求大佬指点。