javascript - 来自预定义集合的组合总和与目标值

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);

Answer 1

你是对的，因为你过滤掉了选择的数字，你不能得到下面的输出

2000 4000 4000

当你把过滤掉的时候，你会得到一个堆栈溢出，因为你没有在partial时停止递归。长度为 3。因此递归调用将 0 添加到 partial永远不会停止递归...因为它们永远不会导致超过目标。

因此将其添加到“基本案例”中:

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);