k-sum 問題
問題描述
給定一個數組及數字 k ,從陣列中找出所有相加結果為 k 的組合。
示例:
給定陣列[1,1,1]
令k=2
,輸出:
[[1,1]]
給定陣列[10, 1, 2, 7, 6, 1, 5]
令k=8
,輸出:
[ [ 1, 2, 5 ], [ 1, 7 ], [ 1, 1, 6 ], [ 2, 6 ] ]
分析
這裡的思路是把k
逐步拆解。既然要找出相加等於k
的元素,那根據遞迴的思想,不難想到假如已經找到了陣列中一個有效的元素,那麼接下來就是從剩餘的元素中繼續去找,相加等於k
減去該元素的那些組合,形成了一個新的子問題。
所以對於第一個結果的查詢,可以從索引為 0 的位置開始遍歷陣列:
-
從候選資料
arr
中取出第一個元素item0
,這樣得到了一個取出該元素後的新陣列arr1
, -
從
k
中減去該元素item0
得到一個新的k0
。 -
如此往復,接下來任務就是需要在新的陣列
arr1
中找出一個組合,其相加結果為k0
。 -
最後必然會進行到
k
為零的時候,此時將前面取出的數組合一起便得到了一個結果。 - 如果陣列都遍歷完了,但 K 最終沒有變成零,說明本次查詢沒有結果。
第二個結果:
- 上面查詢結束,開始從原陣列中第二個位置開始重複上面的步驟。
...
直到進行到陣列的最後一個元素。將前面得到的結果組合後返回。
實現
根據上面的分析得出如下的實現:
/** * k-sum 實現,從候選陣列中找出所有相加結果為 k 的組合 * @param {*} arr 候選陣列 * @param {*} k 目標數字 */ function ksum(arr, k) { var result = []; function process(input, tmpK, tmpResult) { tmpResult = tmpResult || []; if (tmpK === 0 && tmpResult.length > 0) { tmpResult.sort((a, b) => a - b); var hasDuplicate = result.some(v => { return v.join("") === tmpResult.join(""); }); if (!hasDuplicate) { result.push(tmpResult); } } else if (tmpK > 0) { for (let i = 0; i < input.length; i++) { const num = input[i]; process(input.slice(i + 1), tmpK - num, tmpResult.concat(num)); } } } process(arr, k); return result; }
測試:
console.log(ksum([1,1,1], 2)); // [ [ 1, 1 ] ] console.log(ksum([10, 1, 2, 7, 6, 1, 5], 8)); // [ [ 1, 2, 5 ], [ 1, 7 ], [ 1, 1, 6 ], [ 2, 6 ] ]