javascript - 查找数组中的一个或多个数字是否可以加起来等于某个数字

Question

假设我有一个像 9 这样的集合数字和一个包含 #s [1,2,4,6,3,9] 的数组。我想知道什么是循环遍历并查看其中一个或多个#s 是否可以加起来为 9 的最佳方法。我最初的想法是:

• 检查当前数组索引值是否等于magicNum
• 如果当前数小于magicNum，则将其与数组中的另一个数相加并不断循环看是否匹配
• 如果上述方法无效，请转到下一个数字并重复。

我的第一个支票很好，但我遇到了另外两个问题。我知道对于初学者来说，除了使用 reduce 之外，可能还需要(也可能不需要)递归函数。算法不是我的强项(目前)，但我渴望并且非常愿意改进。任何类型的指导都将不胜感激。

const magicNum = 9;

const arr = [10,1,2,4,6,3];

for (let i = 0, arrLength = arr.length; i < arrLength; i++) {
  if (arr[i] === magicNum) {
    console.log('Number Found!');
    continue;
  } else if (arr[i] > magicNum) {
    continue;
  } else if (arr[i] < magicNum) {
    // Stuck here
  }
}

Answer 1

您可以采用迭代和递归的方法来查找子集和。

function getSubsets(array, sum) {

    function fork(i = 0, s = 0, t = []) {
        if (s === sum) {
            result.push(t);
            return;
        }
        if (i === array.length) {
            return;
        }
        if (s + array[i] <= sum) { // shout circuit for positive numbers only
            fork(i + 1, s + array[i], t.concat(array[i]));
        }
        fork(i + 1, s, t);
    }

    var result = [];
    fork();
    return result;
}

console.log(getSubsets([10, 1, 2, 4, 6, 3], 9));

.as-console-wrapper { max-height: 100% !important; top: 0; }

为了仅获取第一个子集，您可以使用第一个找到的值数组退出递归。

function getFirstSubset(array, sum) {

    function fork(i = 0, s = 0, t = []) {
        if (s === sum) {
            return  t;
        }
        if (i === array.length) {
            return;
        }
        return fork(i + 1, s + array[i], t.concat(array[i]))
            || fork(i + 1, s, t);
    }

    return fork();
}

console.log(getFirstSubset([10, 1, 2, 4, 6, 3], 9));

.as-console-wrapper { max-height: 100% !important; top: 0; }