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

Question

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

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

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

看起来解决方案是使用递归函数，但我不太清楚该怎么做。我查看了 Whosebug 上的几个子集求和示例，但 none 似乎符合这种特定情况。

这不是作业题。任何帮助，将不胜感激。这是我的 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

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

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]。返回的 sub-arrays 将保持所选元素的顺序，例如：[3,3,3]、[3,4,2] 和 [6,2,1] 可能是针对该示例输入以 3 个值定位 9 的解决方案.

数字必须都是non-negative。如果允许负值，则必须从代码中删除优化 if (leftOver < 0) return;。

Answer 2

function sumPermutations(target, range, number) {
  var result = [];

  function combo(left, group, sum) {
    if(sum > target) return null;
    if (left == 0) {
      if(sum == target) return group;
      return null;
    }
    
    for (var i = range.min; i <= range.max; i++) {
       var r = combo(left - 1, group.concat(i), sum + i);
      if (r)
        result.push(r);
    }
  }
  combo(number, [], 0);

  return result;
}

console.log(sumPermutations(7, {min: 1, max: 5}, 3));

注意：这给出了重复的结果（所有排列包括具有不同顺序的排列）。您可以通过对数组进行排序并加入它们的项目并将它们散列到散列对象中来删除重复项。

Answer 3

嗯，您可能正在寻找的是 Dynamic Programming. It is an approach where you define mathematically your problem and a recursive solution. Then you try to find a solution, using memoization。

我会制作一个辅助函数，其中的参数是 (range, target, lengthOfResult)。然后做类似的事情：

func helper(arr, target, lengthOfResult){
    if(taget == 0) continue;
    for(int i=1; i<arr.length-1; i++){
        if(taget - arr[i] < 0) return [];
        var sub_results = helper(arr, taget - arr[i], lengthOfResult - 1)
        foreach(var res in sub_results){
            result.concat([arr[i]] + res);
        }
    }
    return result;
}

所以您正在将辅助函数的问题更改为 "Give me all lists of length-1 which sums up to taget-arr[i]"，附加到 arr[i]。然后用它来构造结果，对于每个 arr[i].

基本上，每次迭代长度都会减少，所以函数会在某个点终止。你从目标中减去你现在拥有的任何数字。所以你的最终结果将达到所需的目标。

请注意，此算法仅适用于正数。如果可以允许否定，则应删除第一个 for-loop.
关于记忆，如果你想允许每个数字只使用一次，你可以使用单个数组。如果您允许结果中重复出现数字（如您的示例），您可能需要一个网格；水平方向是目标，垂直方向是 lengthOfResult。然后在每次调用辅助方法的开始时，检查您是否已经计算出该值。这将为您节省一些递归调用并使算法不是指数的。

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

Recursion to find n numbers in a range that add up to a target value

javascript

recursion

sum

subset-sum

备注