javascript - 使用一组数字相加得出特定数字

Question

我一直在尝试找出一种有效的方法，从数组中查找加起来等于给定数字的多个数字。在本例中，我试图找到 3 个数字来合计目标数字。

下面有一个基本的工作示例，但不幸的是递归循环失败了，看起来它不断循环有问题。理想情况下，它会找到第一个可能的答案并返回它，但是当它找不到答案时，它会陷入循环并破坏浏览器。

警告:以下代码将因内存泄漏而中断:

let array = [5,6,3,3,6,67,2,2,6,7,7,2,1,3,4,5,67,7,4,2,5,6,3,3,6,67,2,2,6,7,7,2,1,3,4,5,67,7,4,2,5,6,3,3,6,67,2,2,6,7,7,2,1,3,4,5,67,7,4,2];

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
$('#input').on('blur', function(e){
  let value = parseInt(e.target.value);
  let result = findSums(array, value, 3);
  if(result.length > 0){
    $('#output').text(result[0]); 
  } else {
    $('#output').text('Nothing found');
  }
  
})

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<h1>Input Number Below</h1>
<input id="input" type="number" />
<code id="output" ></code>

Answer 1

嗯，当我测试时，它没有损坏，但仍然有一些提示:

您应该对计数设置额外的限制。您调用的电话太多了。当您的函数处理非常大的总和、小数字和小计数时，它会再次调用自身，直到达到或溢出所需的总和，只有在此之后它才会检查当前计数。所以你应该添加

if (selection.length > count) return;

还有。正如我所见，您的数组中有许多重复项，因此我假设允许使用相同的数字，但前提是它是从另一个索引中获取的。在循环中，您将使用相同的起始索引调用下一个recurse。我想，你需要

for (var i = start; i < arr.length; i++) {
    recurse(i + 1, leftOver-arr[i], selection.concat(arr[i]));
}

最后。这不会影响算法的递归部分，但也许您想过滤掉相同的结果，或者过滤掉数组以删除所有重复项。

希望这有帮助。

编辑:抱歉，错过了有关第一个可能的解决方案的部分。以下是实现这一目标的方法:

function recurse(start, leftOver, selection) {
  if (leftOver < 0) return false; // failure
  if (selection.length > count) return false;
  if (leftOver === 0 && selection.length == count) {
      result.push(selection); // add solution
      return true;
  }
  for (var i = start; i < arr.length; i++) {
      var res = recurse(i + 1, leftOver-arr[i], selection.concat(arr[i]));
      if (res) return true;
  }
}