切片值为什么会变化？

Question

The value of a slice that be appended to a two-dimension slice, is changed later。 Why does it happen?

The full code is below:

import "sort"
import "fmt"

func combinationSum(candidates []int, target int) [][]int {
    sort.Ints(candidates)
    var ret [][]int
    var curlist []int
    combinationSumRecursive(candidates, target, 0, curlist, &ret)
    fmt.Println("ret", ret)
    return ret
}

func combinationSumRecursive(candidates []int, target int, curCandidateIdx int, curlist []int, ret *[][]int) {
    if target == 0 {
        fmt.Println("put", curlist)
        *ret = append(*ret, curlist)
        return
    }
    for i:=curCandidateIdx;i<len(candidates);i++{
        if candidates[i] > target {
            break
        }
        combinationSumRecursive(candidates, target - candidates[i], i, append(curlist, candidates[i]), ret)
    }
}

INPUT is :

[7,3,2]
18

OUTPUT is below:

put [2 2 2 2 2 2 2 2 2]
put [2 2 2 2 2 2 3 3]
put [2 2 2 2 3 7]
put [2 2 2 3 3 3 3]
put [2 2 7 7]
put [2 3 3 3 7]
put [3 3 3 3 3 3]
ret [[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]]

The second slice in ret is changed. [2 2 2 2 2 2 3 3] was expected.

Thanks to any help.

Answer 1

This is caused by the change of the slice curlist in the append on line combinationSumRecursive(candidates, target - candidates[i], i, append(curlist, candidates[i]), ret).

A solution is to reassign curlist to the appended result before passing it to the next recursive level.

package main

import "sort"
import "fmt"

func combinationSum(candidates []int, target int) [][]int {
    sort.Ints(candidates)
    var ret [][]int
    var curlist []int
    combinationSumRecursive(candidates, target, 0, curlist, &ret)
    fmt.Println("ret", ret)
    return ret
}

func combinationSumRecursive(candidates []int, target int, curCandidateIdx int, curlist []int, ret *[][]int) {
    if target == 0 {
        fmt.Println("put", curlist)
        *ret = append(*ret, curlist)
        return
    }
    for i := curCandidateIdx; i < len(candidates); i++ {
        if candidates[i] > target {
            break
        }
        curlist = append(curlist, candidates[i])
        combinationSumRecursive(candidates, target-candidates[i], i, curlist, ret)
    }
}

func main() {
    combinationSum([]int{7, 3, 2}, 18)
}

This yields:

put [2 2 2 2 2 2 2 2 2]
put [2 2 2 2 2 2 3 3]
put [2 2 2 2 3 7]
put [2 2 2 3 3 3 3]
put [2 2 7 7]
put [2 3 3 3 7]
put [3 3 3 3 3 3]
ret [[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]]

[EDIT] First read this. That explains that although you see the addresses of the slice headers change the backing array can still be the same after an append.

Then this is an example of what happens in your case. The problem is in your case is it hard to see because of the recursive calls and the re positioning of the current index into curlist.