Slice append change other elements in Slice

Question

I'm solving Leetcode question at https://leetcode.com/problems/subsets with Golang and iterative solution. The algorithm is basically trying to add the new element to the existing array. After all, it will generate all of the subsets.

But when some elements added to the existing array solution, it change the other element also. Here's the code I provided. I put some debugging Println also.

package main

import (
    "fmt"
)

func main() {
    fmt.Println(subsets([]int{0, 1, 2, 3, 4}))
}

func subsets(nums []int) [][]int {
    res := [][]int{}

    res = append(res, []int{})
    for i := 0; i < len(nums); i++ {
        for j := range res {
            fmt.Println(i)
            temp := append(res[j], nums[i])
            fmt.Println(temp)
            res = append(res, temp)
            fmt.Println(res)
        }
    }

    return res
}

Output

0
[0]
[[] [0]]
1
[1]
[[] [0] [1]]
1
[0 1]
[[] [0] [1] [0 1]]
2
[2]
[[] [0] [1] [0 1] [2]]
2
[0 2]
[[] [0] [1] [0 1] [2] [0 2]]
2
[1 2]
[[] [0] [1] [0 1] [2] [0 2] [1 2]]
2
[0 1 2]
[[] [0] [1] [0 1] [2] [0 2] [1 2] [0 1 2]]
3
[3]
[[] [0] [1] [0 1] [2] [0 2] [1 2] [0 1 2] [3]]
3
[0 3]
[[] [0] [1] [0 1] [2] [0 2] [1 2] [0 1 2] [3] [0 3]]
3
[1 3]
[[] [0] [1] [0 1] [2] [0 2] [1 2] [0 1 2] [3] [0 3] [1 3]]
3
[0 1 3]
[[] [0] [1] [0 1] [2] [0 2] [1 2] [0 1 2] [3] [0 3] [1 3] [0 1 3]]
3
[2 3]
[[] [0] [1] [0 1] [2] [0 2] [1 2] [0 1 2] [3] [0 3] [1 3] [0 1 3] [2 3]]
3
[0 2 3]
[[] [0] [1] [0 1] [2] [0 2] [1 2] [0 1 2] [3] [0 3] [1 3] [0 1 3] [2 3] [0 2 3]]
3
[1 2 3]
[[] [0] [1] [0 1] [2] [0 2] [1 2] [0 1 2] [3] [0 3] [1 3] [0 1 3] [2 3] [0 2 3] [1 2 3]]
3
[0 1 2 3]
[[] [0] [1] [0 1] [2] [0 2] [1 2] [0 1 2] [3] [0 3] [1 3] [0 1 3] [2 3] [0 2 3] [1 2 3] [0 1 2 3]]
4
[4]
[[] [0] [1] [0 1] [2] [0 2] [1 2] [0 1 2] [3] [0 3] [1 3] [0 1 3] [2 3] [0 2 3] [1 2 3] [0 1 2 3] [4]]
4
[0 4]
[[] [0] [1] [0 1] [2] [0 2] [1 2] [0 1 2] [3] [0 3] [1 3] [0 1 3] [2 3] [0 2 3] [1 2 3] [0 1 2 3] [4] [0 4]]
4
[1 4]
[[] [0] [1] [0 1] [2] [0 2] [1 2] [0 1 2] [3] [0 3] [1 3] [0 1 3] [2 3] [0 2 3] [1 2 3] [0 1 2 3] [4] [0 4] [1 4]]
4
[0 1 4]
[[] [0] [1] [0 1] [2] [0 2] [1 2] [0 1 2] [3] [0 3] [1 3] [0 1 3] [2 3] [0 2 3] [1 2 3] [0 1 2 3] [4] [0 4] [1 4] [0 1 4]]
4
[2 4]
[[] [0] [1] [0 1] [2] [0 2] [1 2] [0 1 2] [3] [0 3] [1 3] [0 1 3] [2 3] [0 2 3] [1 2 3] [0 1 2 3] [4] [0 4] [1 4] [0 1 4] [2 4]]
4
[0 2 4]
[[] [0] [1] [0 1] [2] [0 2] [1 2] [0 1 2] [3] [0 3] [1 3] [0 1 3] [2 3] [0 2 3] [1 2 3] [0 1 2 3] [4] [0 4] [1 4] [0 1 4] [2 4] [0 2 4]]
4
[1 2 4]
[[] [0] [1] [0 1] [2] [0 2] [1 2] [0 1 2] [3] [0 3] [1 3] [0 1 3] [2 3] [0 2 3] [1 2 3] **[0 1 2 3]** [4] [0 4] [1 4] [0 1 4] [2 4] [0 2 4] [1 2 4]]
4
[0 1 2 4]
[[] [0] [1] [0 1] [2] [0 2] [1 2] [0 1 2] [3] [0 3] [1 3] [0 1 3] [2 3] [0 2 3] [1 2 3] **[0 1 2 4]** [4] [0 4] [1 4] [0 1 4] [2 4] [0 2 4] [1 2 4] [0 1 2 4]]
4
[3 4]
[[] [0] [1] [0 1] [2] [0 2] [1 2] [0 1 2] [3] [0 3] [1 3] [0 1 3] [2 3] [0 2 3] [1 2 3] [0 1 2 4] [4] [0 4] [1 4] [0 1 4] [2 4] [0 2 4] [1 2 4] [0 1 2 4] [3 4]]
4
[0 3 4]
[[] [0] [1] [0 1] [2] [0 2] [1 2] [0 1 2] [3] [0 3] [1 3] [0 1 3] [2 3] [0 2 3] [1 2 3] [0 1 2 4] [4] [0 4] [1 4] [0 1 4] [2 4] [0 2 4] [1 2 4] [0 1 2 4] [3 4] [0 3 4]]
4
[1 3 4]
[[] [0] [1] [0 1] [2] [0 2] [1 2] [0 1 2] [3] [0 3] [1 3] [0 1 3] [2 3] [0 2 3] [1 2 3] [0 1 2 4] [4] [0 4] [1 4] [0 1 4] [2 4] [0 2 4] [1 2 4] [0 1 2 4] [3 4] [0 3 4] [1 3 4]]
4
[0 1 3 4]
[[] [0] [1] [0 1] [2] [0 2] [1 2] [0 1 2] [3] [0 3] [1 3] [0 1 3] [2 3] [0 2 3] [1 2 3] [0 1 2 4] [4] [0 4] [1 4] [0 1 4] [2 4] [0 2 4] [1 2 4] [0 1 2 4] [3 4] [0 3 4] [1 3 4] [0 1 3 4]]
4
[2 3 4]
[[] [0] [1] [0 1] [2] [0 2] [1 2] [0 1 2] [3] [0 3] [1 3] [0 1 3] [2 3] [0 2 3] [1 2 3] [0 1 2 4] [4] [0 4] [1 4] [0 1 4] [2 4] [0 2 4] [1 2 4] [0 1 2 4] [3 4] [0 3 4] [1 3 4] [0 1 3 4] [2 3 4]]
4
[0 2 3 4]
[[] [0] [1] [0 1] [2] [0 2] [1 2] [0 1 2] [3] [0 3] [1 3] [0 1 3] [2 3] [0 2 3] [1 2 3] [0 1 2 4] [4] [0 4] [1 4] [0 1 4] [2 4] [0 2 4] [1 2 4] [0 1 2 4] [3 4] [0 3 4] [1 3 4] [0 1 3 4] [2 3 4] [0 2 3 4]]
4
[1 2 3 4]
[[] [0] [1] [0 1] [2] [0 2] [1 2] [0 1 2] [3] [0 3] [1 3] [0 1 3] [2 3] [0 2 3] [1 2 3] [0 1 2 4] [4] [0 4] [1 4] [0 1 4] [2 4] [0 2 4] [1 2 4] [0 1 2 4] [3 4] [0 3 4] [1 3 4] [0 1 3 4] [2 3 4] [0 2 3 4] [1 2 3 4]]
4
[0 1 2 4 4]
[[] [0] [1] [0 1] [2] [0 2] [1 2] [0 1 2] [3] [0 3] [1 3] [0 1 3] [2 3] [0 2 3] [1 2 3] [0 1 2 4] [4] [0 4] [1 4] [0 1 4] [2 4] [0 2 4] [1 2 4] [0 1 2 4] [3 4] [0 3 4] [1 3 4] [0 1 3 4] [2 3 4] [0 2 3 4] [1 2 3 4] [0 1 2 4 4]]
[[] [0] [1] [0 1] [2] [0 2] [1 2] [0 1 2] [3] [0 3] [1 3] [0 1 3] [2 3] [0 2 3] [1 2 3] [0 1 2 4] [4] [0 4] [1 4] [0 1 4] [2 4] [0 2 4] [1 2 4] [0 1 2 4] [3 4] [0 3 4] [1 3 4] [0 1 3 4] [2 3 4] [0 2 3 4] [1 2 3 4] [0 1 2 4 4]]

When it add the [0 1 2 4] element, it also change the existing [0 1 2 3] to [0 1 2 4]. Is there any specific reason why this happen?

`append` may potentially change the contents of the underlying array. So after you append to a slice - the slice you appended to is not guaranteed to stay the same. — zerkms, Dec 06 '17 at 01:53
This answer directly answers your question: [Concatenate two slices in Go](https://stackoverflow.com/questions/16248241/concatenate-two-slices-in-go/40036950#40036950) — icza, Dec 06 '17 at 08:02

Vane Trajkov · Accepted Answer · 2017-12-06T03:04:09.687

1

In your append function calls you are using slices meaning you work with references, thus no guarantee that the values will remain static as @zerkms mentioned. What you can do is create a copy of the slice temp returned from the 1st append call and use it in the 2nd append. This will make passing a copy of the temp slice and with that avoiding any interferences.

package main

import (
    "fmt"
)

func main() {
    fmt.Println(subsets([]int{0, 1, 2, 3, 4}))
}

func subsets(nums []int) [][]int {
    res := [][]int{}

    res = append(res, []int{})
    for i := 0; i < len(nums); i++ {
        for j := range res {
            fmt.Println(i)
            temp := append(res[j], nums[i])
            copy_temp := make([]int, len(temp))
            copy(copy_temp, temp)
            fmt.Println(copy_temp)
            res = append(res, copy_temp)
            fmt.Println(res)
        }
    }

    return res
}

edited Dec 06 '17 at 03:04

answered Dec 06 '17 at 02:37

Vane Trajkov

758
4
11

Thanks for the answer. Is this a heavy operation? I thought that I can use slice the same as I used ArrayList in Java or vector in cpp – Chandra Pratama Dec 06 '17 at 02:50
Not sure how ArrayList in Java or vector in cpp behave but what I can say that we should be careful working with slices as they are pointers to piece of an underlying array, as the docs say `A slice is not an array. A slice describes a piece of an array.`. In this case, you have no choice than to create a copy of the slice you want to pass around and use it in more operations. This will guarantee you that no funky business will happen in the background when the same existing slice is trying to relocate memory to accommodate new writes. - https://blog.golang.org/slices – Vane Trajkov Dec 06 '17 at 03:14

Slice append change other elements in Slice

1 Answers1