Error when using pointers to append into slice [][]int

Question

While I was trying to solve a problem "Subset II" from LC, I came across a strange problem. The code generates a power set from a given set. However, when I run the code it failed because one of the set wasn't correct.

The set [0,3,5,7] replaced by [0,3,5,9] (hence gets appended twice).

I have a print statement (highlighted in code) right before a set gets appended to res, and it prints the correct power set.

The only issue I could think is the use of pointers to append values into a slice, however since it's does not run concurrently I don't see why there would be a race condition. Appreciate if someone can point out my mistake.

package main

import (
    "fmt"
    "sort"
)

func ValueCount( nums []int) map[int]int{
  hm := make(map[int]int)
  for _,v := range(nums){
    if c, ok := hm[v]; ok {
      hm[v] = c + 1
    }else{
      hm[v] = 1
    }
  }
  return hm
}

func subsetsWithDup(nums []int) [][]int {
    var res [][]int
    res = append(res,[]int{})
    sort.Ints(nums)
  hashMap := ValueCount(nums)
  var t []int
  printTest(nums, t, &res, hashMap)
    return res
}


func printTest(nums []int, t []int, res *[][]int, hm map[int]int) {
  if len(nums) == 0 {
    return
  }
  for i:= 0; i < len(nums); {
    v := nums[i]
    x := nums[i:]
    for  k:= 0; k< hm[v]; k++ {
      var a,b []int
      for z:= 0; z<k+1; z++ { 
        a = append(t,x[z])
      }
      fmt.Println(a) // <--------- Prints the values that gets appended to res
      *res = append(*res, a)    
      b = a
      printTest(nums[i+hm[v]:], b, res, hm)
    }
    i += hm[v]
  }
  
}

func main(){
    n := []int{9,0,3,5,7}
    fmt.Println("Find the power set of:", n)
    fmt.Println(subsetsWithDup(n))
}

// [0,3,5,7] changes to 
// [0,3,5,9] in the output

Answer 1

The bug occurs on line 40:

a = append(t, x[z])

A quick fix would be to change this for loop:

        for k := 0; k < hm[v]; k++ {
            var a, b []int
            for z := 0; z < k+1; z++ {
                a = append(t, x[z])
            }
            fmt.Println(a) // <--------- Prints the values that gets appended to res
            *res = append(*res, a)
            b = a
            printTest(nums[i+hm[v]:], b, res, hm)
        }

To this:

        for k := 0; k < hm[v]; k++ {
            var a, b []int
            a = make([]int, len(t))
            copy(a, t)
            for z := 0; z < k+1; z++ {
                a = append(a, x[z])
            }
            fmt.Println(a) // <--------- Prints the values that gets appended to res
            *res = append(*res, a)
            b = a
            printTest(nums[i+hm[v]:], b, res, hm)
        }

It has to do with how Go uses slices as a data structure. When the first argument to the built-in append function was a slice argument, it copied some of the slice's internal data that wasn't intuitive to the programmer. It then modified the argument slice, t, and the newly created slice, a.

I'd recommend reading up on slice internals if you're interested in learning more.

Full program edited:

package main

import (
    "fmt"
    "sort"
)

func ValueCount(nums []int) map[int]int {
    hm := make(map[int]int)
    for _, v := range nums {
        if c, ok := hm[v]; ok {
            hm[v] = c + 1
        } else {
            hm[v] = 1
        }
    }
    return hm
}

func subsetsWithDup(nums []int) [][]int {
    var res [][]int
    res = append(res, []int{})
    sort.Ints(nums)
    hashMap := ValueCount(nums)
    var t []int
    printTest(nums, t, &res, hashMap)
    return res
}

func printTest(nums []int, t []int, res *[][]int, hm map[int]int) {
    if len(nums) == 0 {
        return
    }
    for i := 0; i < len(nums); {
        v := nums[i]
        x := nums[i:]
        for k := 0; k < hm[v]; k++ {
            var a, b []int
            a = make([]int, len(t))
            copy(a, t)
            for z := 0; z < k+1; z++ {
                a = append(a, x[z])
            }
            fmt.Println(a) // <--------- Prints the values that gets appended to res
            *res = append(*res, a)
            b = a
            printTest(nums[i+hm[v]:], b, res, hm)
        }
        i += hm[v]
    }

}

func main() {
    n := []int{9, 0, 3, 5, 7}
    fmt.Println("Find the power set of:", n)
    fmt.Println(subsetsWithDup(n))
}

New output:

Find the power set of: [9 0 3 5 7]
[0]
[0 3]
[0 3 5]
[0 3 5 7]
[0 3 5 7 9]
[0 3 5 9]
[0 3 7]
[0 3 7 9]
[0 3 9]
[0 5]
[0 5 7]
[0 5 7 9]
[0 5 9]
[0 7]
[0 7 9]
[0 9]
[3]
[3 5]
[3 5 7]
[3 5 7 9]
[3 5 9]
[3 7]
[3 7 9]
[3 9]
[5]
[5 7]
[5 7 9]
[5 9]
[7]
[7 9]
[9]
[[] [0] [0 3] [0 3 5] [0 3 5 7] [0 3 5 7 9] [0 3 5 9] [0 3 7] [0 3 7 9] [0 3 9] [0 5] [0 5 7] [0 5 7 9] [0 5 9] [0 7] [0 7 9] [0 9] [3] [3 5] [3 5 7] [3 5 7 9] [3 5 9] [3 7] [3 7 9] [3 9] [5] [5 7] [5 7 9] [5 9] [7] [7 9] [9]]

Answer 2

Be very careful using (and reusing) slice results - especially when altering those slice values later. Since slices have backing arrays, the referenced data can change in very unexpected ways!

A quick fix to your problem is to copy slice results to a new slice. This ensures changes to the original slice do not introduce bugs (especially in a recursive algorithm).

To copy a slice:

func copyIntSlice(a []int) []int {
    c := make([]int, len(a))
    copy(c, a) // `a` can now grow/shrink/change without affecting `c`
    return c
}

and just call this from your main code:

aCopy := copyIntSlice(a)
*res = append(*res, aCopy)

printTest(nums[i+hm[v]:], aCopy, res, hm)

https://play.golang.org/p/1p8Z4sV9foQ