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 ] ]