I am trying to solve some dynamic programming problems by using Golang. I wrote a function like
func main() {
fmt.Println(HowSum(5, []int{1, 2, 5}))
}
func HowSum(targetNum int, numbers []int) []int {
retAry = make([][]int, targetNum 1)
retAry[0] = make([]int, 0)
for i := 0; i <= targetNum; i {
if retAry[i] != nil {
for _, num := range numbers {
if i num <= targetNum {
fmt.Print("Before:", i, " round, num =", num, retAry, "\n")
retAry[i num] = append(retAry[i], num)
fmt.Print("After :", i, " round, num =", num, retAry, "\n\n")
}
}
}
}
return retAry[targetNum]
}
A part of results is as follows.
...
Before:3 round, num =2 [[] [1] [1 1] [1 1 1] [1 1 1 1] [5]]
After :3 round, num =2 [[] [1] [1 1] [1 1 1] [1 1 1 2] [1 1 1 2]]
...
[1 1 1 2 1]
The array in retAry[4] is changed from [1 1 1 1] to [1 1 1 2] when the program replace retAry[5] from [5] to [1 1 1 2]. What happen?
However, if replace
retAry[i num] = append(retAry[i], num)
to retAry[i num] = append([]int{num}, retAry[i]...)
, I can get the correct answer.
...
Before:3 round, num =2 [[] [1] [1 1] [1 1 1] [1 1 1 1] [5]]
After :3 round, num =2 [[] [1] [1 1] [1 1 1] [1 1 1 1] [2 1 1 1]]
...
[1 1 1 1 1]
Could anyone can help to explain what mistake I made?
The code is here
CodePudding user response:
However, if replace retAry[i num] = append(retAry[i], num) to retAry[i num] = append([]int{num}, retAry[i]...) , I can get the correct answer.
Explain:
retAry[i num] = append(retAry[i], num)
is sharing the same array between retAry[i num] and retAry[i]. If you modify one slice, other slice could be changed as well.
func main() {
s1 := append([]int{}, 1, 2, 3) // len: 3, cap 4 []int{1, 2, 3, 0}
// it appends 4 to 4th index and assign new slice to s2.
// s2 is share the same array with s1
// s1 : len: 3, cap 4 []int{1, 2, 3, 4}
// s2 : len: 4, cap 4 []int{1, 2, 3, 4}
s2 := append(s1, 4)
// s3 is share the same array with s1 and s2 as well
// when you append 4th index to s1, and assign to s3, both s1 and s2 will change as well
// s1 : len: 3, cap 4 []int{1, 2, 3, 5}
// s2 : len: 4, cap 4 []int{1, 2, 3, 5}
// s3 : len: 4, cap 4 []int{1, 2, 3, 5}
s3:= append(s1, 5)
fmt.Println(s2, s3) // output [1 2 3 5] [1 2 3 5]
}
retAry[i num] = append([]int{num}, retAry[i]...)
[]int{num}
you initialize a new slice with a new array, and then append every elements in retAry[i] to the new array. They aren't any reference between retAry[i num] and retAry[i] anymore.