k-sum 问题
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 ] ]