組み合わせの合計

Question

/* 
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 
} 

これはLeetcodeの問題で、私はそれを解決するために再帰を使用します。

18行目では、合計がターゲットと等しい場合にすべての場合を出力します。

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

そして、それは私が欲しいの答えです： 出力されます！ しかし、なぜ最終的な答え（二次元）である：

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

予想答えは：[1,1,1,1]、[1,1,2]、[2,2]

コード内の誤りを見つけてください。御時間ありがとうございます。

Answer 1

これは、スライスの仕組みが原因で発生します。スライスオブジェクトは、スライスの長さ、配列内のスライスの開始点へのポインタ、およびスライスの容量とともに、基本となる配列への参照です。スライスの容量は、スライスの先頭から配列の最後までの要素の数です。スライスに追加すると、新しい要素に使用可能な容量がある場合、既存の配列に追加されます。ただし、十分な容量がない場合は、appendは新しい配列を割り当てて要素をコピーします。新しい配列には余分な容量が割り当てられているため、すべての追加で割り当てが不要です。十分なスペースが新たな要素の配列にありますので、再配分の原因とどちらもあなたのforループでは

、curCombは[1, 1, 1]あり、その容量は、ループの連続した繰り返し4.あるとき、あなたは1を追加してから2、 。 curCombが[1, 1, 1, 1]の場合、結果リストに表示されますが、forループの次の繰り返しでは、appendは最後の要素を2に変更します（これは基本的な配列であることに注意してください）。最後に結果が出る。

これに対する解決策は、合計が目標と等しいときcurCombのコピーを返すことです：

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

This articleは、スライスがどのように動作するかの良い説明を与えます。