CODEWITHSUNDEEP
recursiongo
Yun Chen
Yun Chen

Reputation: 23

Combination Sum in Go

/*
Given an array: [1,2] and a target: 4
Find the solution set that adds up to the target
in this case:
[1,1,1,1]
[1,1,2]
[2,2]
*/
import "sort"
func combinationSum(candidates []int, target int) [][]int {
    sort.Ints(candidates)
    return combine(0, target, []int{}, candidates)
}
func combine(sum int, target int, curComb []int, candidates []int) [][]int {
    var tmp [][]int
    var result [][]int
    if sum == target {
        fmt.Println(curComb)
        return [][]int{curComb}
    } else if sum < target {
        for i,v := range candidates {
            tmp = combine(sum+v, target, append(curComb, v), candidates[i:])
            result = append(result,tmp...)
        }
    }
    return result
}

This is a problem in Leetcode and I use recursion to solve it.

In line 18, I print every case when the sum is equal to the target. The output is :

[1,1,1,1]
[1,1,2]
[2,2]

And that is the answer that I want! But why is the final answer (two-dimensional):

[[1,1,1,2],[1,1,2],[2,2]]

Expected answer is : [[1,1,1,1],[1,1,2],[2,2]]

Please help me find the mistake in the code. Thanks for your time.

Upvotes: 2

Views: 1194

Answers (1)

Andy Schweig
Andy Schweig

Reputation: 6739

This happens because of the way slices work. A slice object is a reference to an underlying array, along with the length of the slice, a pointer to the start of the slice in the array, and the slice's capacity. The capacity of a slice is the number of elements from the beginning of the slice to the end of the array. When you append to a slice, if there is available capacity for the new element, it is added to the existing array. However, if there isn't sufficient capacity, append allocates a new array and copies the elements. The new array is allocated with extra capacity so that an allocation isn't required for every append.

In your for loop, when curComb is [1, 1, 1], its capacity is 4. On successive iterations of the loop, you append 1 and then 2, neither of which causes a reallocation because there's enough room in the array for the new element. When curComb is [1, 1, 1, 1], it is put on the results list, but in the next iteration of the for loop, the append changes the last element to 2 (remember that it's the same underlying array), so that's what you see when you print the results at the end.

The solution to this is to return a copy of curComb when the sum equals the target:

if sum == target {
    fmt.Println(curComb)
    tmpCurComb := make([]int, len(curComb))
    copy(tmpCurComb, curComb)
    return [][]int{tmpCurComb}

This article gives a good explanation of how slices work.

Upvotes: 2

Related Questions