doumiyi7063
2019-02-25 04:30 阅读 25
已采纳

golang组合生成出错

I'm dealing with a programming problem

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

and with input n = 5, k = 4, the output should be [[1,2,3,4],[1,2,3,5],[1,2,4,5],[1,3,4,5],[2,3,4,5]], the following is my golang solution

func combine(n int, k int) [][]int {
    result := [][]int{}
    comb := []int{}
    subcom(0, k, n, &comb, &result)
    return result
}

func subcom(s, k, n int, comb *[]int, result *[][]int) {
    if k > 0 {
        for i := s + 1; i <= n-k+1; i++ {
            c := append(*comb, i)
            subcom(i, k-1, n, &c, result)
        }
    } else {
        *result = append(*result, *comb)
    }
}

I think my solution is right, but it return [[1 2 3 5] [1 2 3 5] [1 2 4 5] [1 3 4 5] [2 3 4 5]].

After debugging, I found [1 2 3 4] was added to the result slice at the beginning, but later changed to [1 2 3 5], resulting in the repetition of two [1 2 3 5]s. But I can't figure out what's wrong here.

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享

1条回答 默认 最新

  • 已采纳
    dse84825 dse84825 2019-02-25 04:52

    This is a common mistake when using append.

    When your code runs c:=append(*comb,i), it tries to first use the allocated memory in the underlying array to add a new item and only create a new slice when it failed to do so. This is what changes the [1 2 3 4] to [1 2 3 5] - because they share the same underlying memory.

    To fix this, copy when you want to append into result:

    now := make([]int,len(*comb))
    copy(now,*comb)
    *result = append(*result,now)
    

    Or use a shortcut of copying:

    *result = append(*result, append([]int{},*comb...))
    

    Update:

    To understand what I mean by underlying memory, one should understandd the internal model of Go's slice.

    In Go, a slice has a data structure called SliceHeader which is accessible through reflect package and is what being referred to when you use unsafe.Sizeof and taking address.

    The SliceHeader taking cares of three elements: Len,Cap and a Ptr. The fisrt two is trivail: they are what len() and cap() is for. The last one is a uintptr that points to the memory of the data the slice is containing.

    When you shallow-copy a slice, a new SliceHeader is created but with the same content, including Ptr. So the underlying memory is not copied, but shared.

    点赞 评论 复制链接分享

相关推荐