CODEWITHSUNDEEP
gocopyslice
jack-nie
jack-nie

Reputation: 736

how to understand the following code about golang slice?

Recently I found some code that I can't understand, below is my code:

func subsetsWithDup(nums []int) [][]int {
    if len(nums) == 0 {
        return [][]int{[]int{}}
    }
    sort.Ints(nums)
    result := [][]int{}
    backtracking(nums, &result, []int{}, 0)
    return result
}

func backtracking(nums []int, result *[][]int, tempList []int, start int) {
    *result = append(*result, tempList)
    for i := start; i < len(nums); i++ {
        if i > start && nums[i] == nums[i-1] {
            continue
        }
        tempList = append(tempList, nums[i])
        backtracking(nums, result, tempList, i+1)
        tempList = tempList[:len(tempList)-1:len(tempList)-1]
    }
}

and another approach:

func subsetsWithDup(nums []int) [][]int {
    sort.Ints(nums)
    return subsets(nums, []int{}, [][]int{})
}

func subsets(nums []int, result []int, results [][]int) [][]int {    
    newR := make([]int, len(result))
    copy(newR, result)
    results = append(results, newR)

    if len(nums) == 0 {return results}

    for i := 0; i < len(nums); i++ {
        if i > 0 && nums[i] == nums[i - 1] {continue}
        result = append(result, nums[i])
        results = subsets(nums[i + 1:], result, results)
        result = result[:len(result) - 1]
    }

    return results
}

In the first approach, I use the following code :

tempList = tempList[:len(tempList)-1:len(tempList)-1]

it works, but if I change it to:

tempList = tempList[:len(tempList)-1]

it dose not work.In the second approach which use copy function also works. I want to know what happens behind the code, any help is appreciated, thanks.

Upvotes: 0

Views: 108

Answers (1)

leaf bebop
leaf bebop

Reputation: 8212

In Go, slice is a pointer type to maintain information about underlying array, so change of the underlying array would cause changes of the slice value, which sometimes might be surprising.

The second part of the puzzle is that append modifies the underlying array if the cap of the slice is sufficient. Document:

The append built-in function appends elements to the end of a slice. If it has sufficient capacity, the destination is resliced to accommodate the new elements. If it does not, a new underlying array will be allocated. Append returns the updated slice. It is therefore necessary to store the result of append, often in the variable holding the slice itself.

So in you failed attempt, tempList = append(tempList, nums[i]) will possibly change value of previously stored slices in result.

On the other hand, the second approach creates a new slice with new underlying array and copy to it explictly, so the error is avoided. The first approach is more subtle, as it use a full slice expressions: tempList[:len(tempList)-1:len(tempList)-1]. The code limits the new slice's cap so append would have to allocate a new underlying array each time instead of using the orignal one.

More about full slice expressions(spec):

For an array, pointer to array, or slice a (but not a string), the primary expression

a[low : high : max]

constructs a slice of the same type, and with the same length and elements as the simple slice expression a[low : high]. Additionally, it controls the resulting slice's capacity by setting it to max - low. Only the first index may be omitted; it defaults to 0. After slicing the array a

a := [5]int{1, 2, 3, 4, 5}
t := a[1:3:5]

the slice t has type []int, length 2, capacity 4, and elements

t[0] == 2
t[1] == 3

Upvotes: 1

Related Questions