预定义集合中的组合求和与目标值

Question

我有以下的代码。我需要找到该数组中所有数字之和为目标值100000的组合。问题在于下面的解决方案并不包括这样一对数字20000 40000 40000。这是因为在每次递归时，我都会取出一个数字(请看 filter功能)。如果我没有使用filter，那么就会发生最大调用栈溢出。

所以最终的任务是找到所有数字之和为目标值的组合，每个组合只应包含3个数字，并且0也要参与。

有什么想法如何解决这个问题吗？

function subsetSum(numbers, target, partial) {
  var s, n, remaining;

  partial = partial || [];

  // sum partial
  s = partial.reduce(function(a, b) {
    return a + b;
  }, 0);

  // check if the partial sum is equals to target
  if (s === target && partial.length === 3) {
    console.log("%s=%s", partial.join("+"), target)
  }

  if (s >= target) {
    return; // if we reach the number why bother to continue
  }

  for (var i = 0; i < numbers.length; i++) {
    n = numbers[i];
    remaining = numbers.filter(num => num != n);
    subsetSum(remaining, target, partial.concat([n]));
  }
}

subsetSum([0, 10000, 20000, 30000, 40000, 50000, 60000, 70000, 80000, 90000], 100000);

- Nika Kurashvili

---

你也得到了想要的结果吗？ - Nina Scholz

"一对": 我想你是指三元组吧？我想你只对三个数的总和感兴趣？ - trincot

不在手边，只在脑海中。我想应该有40多个条目，所以我不能发布它。这个想法很简单：每个组合应该包含3个数字，每个组合的总和应该是目标，并且组合应该包含重复项。 - Nika Kurashvili

@trincot 是的..这就是为什么我有 partial.length === 3 - Nika Kurashvili

好的，但是“pair”意味着两个。这很令人困惑。 - trincot

Answer 1

你说得对，因为你过滤了选定的数字，所以无法获得以下输出。

2000 4000 4000

当你取消筛选时，会出现堆栈溢出，因为当partial的长度为3时，递归未停止。因此，继续向partial中添加0的递归调用永远不会停止递归...因为它们永远不会超过目标。

所以将其添加到“基本情况”中：

function subsetSum(numbers, target, partial) {
  var s, n, remaining;

  partial = partial || [];

  // sum partial
  s = partial.reduce(function(a, b) {
    return a + b;
  }, 0);

  // check if the partial sum is equals to target
  if (s === target && partial.length === 3) {
    console.log("%s=%s", partial.join("+"), target)
  }

  if (s >= target || partial.length === 3) {
    return; // if we reach the number or maximum length don't bother to continue
  }

  for (var i = 0; i < numbers.length; i++) {
    n = numbers[i];
    subsetSum(numbers, target, partial.concat([n]));
  }
}

subsetSum([0, 10000, 20000, 30000, 40000, 50000, 60000, 70000, 80000, 90000], 100000);

- trincot