javascript - 递归查找范围内加起来等于目标值的 n 个数字

Question

我编写了一个函数，在给定从 0 到 x 的数字范围的情况下，找到所有两个数字的总和目标值的集合。我正在尝试以某种方式重写它，以便您可以获得给定长度 n(不仅是 2)的结果，而且 n 个数字加在一起时将等于目标。

例如，如果范围是 1 到 5，并且您想要找到所有三个数字加起来等于 7 的集合，答案将是:

[[1,1,5], [1,2,4], [1,3,3], [2,2,3]]

看起来解决方案是使用递归函数，但我不太清楚该怎么做。我查看了 StackOverflow 上的几个子集求和示例，但似乎没有一个与这个特定场景相匹配。

这不是作业题。任何帮助，将不胜感激。这是我的 findPairs 函数:

function findPairs(arr, target) {
    var pairs = [];
    var first = 0;
    var last = arr.length-1;
    while (first <= last) {
      var sum = arr[first] + arr[last];
      if (sum === target) {
        pairs.push([arr[first], arr[last]]);
        first ++;
        last--;
      }
      else if (sum < target) {
        first++;
      }
      else {
        last--;
      }
    }
    return pairs;
  }

  var sample = _.range(11);
  console.log(JSON.stringify(findPairs(sample,12)));
  // Returns
  // [[2,10],[3,9],[4,8],[5,7],[6,6]]

此示例使用 lodash _.range 函数。在这里 fiddle :https://jsfiddle.net/tbarmann/muoms1vL/10/

Answer 1

您确实可以使用递归。将第三个参数定义为要查找的子数组的长度，并在该函数内部定义一个递归函数，如下所示:

function findSums(arr, target, count) {
    var result = [];
    function recurse(start, leftOver, selection) {
        if (leftOver < 0) return; // failure
        if (leftOver === 0 && selection.length == count) {
            result.push(selection); // add solution
            return;
        }
        for (var i = start; i < arr.length; i++) {
            recurse(i, leftOver-arr[i], selection.concat(arr[i]));
        }
    }
    recurse(0, target, []);
    return result;
}
// Demo
var result = findSums([1,2,3,4,5], 7, 3);
console.log(result);   

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

备注

该解决方案不要求输入数组具有连续的数字(范围):您可以传递它 [3,6,4,2,1] .返回的子数组将保持所选元素的顺序，例如:[3,3,3] , [3,4,2]和 [6,2,1]可能是针对该示例输入以 3 个值定位 9 的解决方案。

数字必须全部为非负数。如果允许负值，则优化 if (leftOver < 0) return;必须从代码中删除。