Weird pointer behavior

[vladazn (Vladimir Aznauryan)]

Hello, I have strange behavior when using pointer. Can please someone explain how is it working?

package main

import "fmt"

func addAndCheck(candidates []int, candidateIndex int, target int, currentTest []int, l int, finalSolution *[][]int) {
	currentTest = append(currentTest, candidates[candidateIndex])
	if target == 0 {
		fmt.Println("currentTest --> ", currentTest)
		*finalSolution = append(*finalSolution, currentTest)
		fmt.Println("current finalResult --> ", *finalSolution)
		return
	}
	if target < 0 {
		return
	}
	for i := candidateIndex; i < l; i++ {
		//fmt.Println(target, candidates[i], i, target-candidates[i], currentTest )
		addAndCheck(candidates, i, target-candidates[i], currentTest, l, finalSolution)
	}
}

func combinationSum(candidates []int, target int) [][]int {
	solution := make([][]int, 0)

	for i, k := range candidates {
		currentTest := make([]int, 0)
		addAndCheck(candidates, i, target-k, currentTest, len(candidates), &solution)
	}
	return solution
}

func main() {
	a := combinationSum([]int{2, 3, 5}, 8)
	fmt.Println("finalResult --> ", a)
}

As you can see in from the code I am appending the result which works for me in the finalResult array. The weird things happens with the first pushed element of the array. Here is the output i receive when printing out the currentTest and finalResult during program execution.

currentTest → [2 2 2 2]
current finalResult → [[2 2 2 2]]
currentTest → [2 3 3]
current finalResult → [[2 2 2 5] [2 3 3]]
currentTest → [3 5]
current finalResult → [[2 2 2 5] [2 3 3] [3 5]]
finalResult → [[2 2 2 5] [2 3 3] [3 5]]

How is it possible that first pushed slice [2 2 2 2] is turning into [2 2 2 5] ?

Thank you for your help in advance.

[skillian (Sean Killian)]

When you append to currentTest, you’re not guaranteed to get new memory every time. Until you get to very high capacities, the current implementation of append doubles the capacity, so you start off with capacity 0, the first appends gives you 1, then 2, but then 4.

Your algorithm goes 4 levels deep into addAndCheck but after the 3rd level, currentTest's capacity is 4, not 3. The first iteration through the 4th level of calls to addAndCheck, produces []int{2, 2, 2, 2}, appends the slice to finalResult, and then returns. Now the 3rd level of addAndCheck continues its loop and tests with 5 by calling into another level of addAndCheck which appends 5 to currentTest[:3] (which is the same actual slice as was appended to finalResult which contains []int{2, 2, 2, 2}, so you get []int{2, 2, 2, 5}.

Here’s the same example with a printTest function that demonstrates the slice memory and recursion: https://play.golang.org/p/_dZAN1u7-4Z

A fix is to slice currentTest with a 3-index slice so that appending always creates a new slice on line 8:

currentTest = append(currentTest[:len(currentTest):len(currentTest)], candidates[candidateIndex])

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

[vladazn (Vladimir Aznauryan)]

Thank you for the detailed answer