使用数字数组相加到特定数字

Question

我一直在努力寻找一种有效的方法来从一个数组中找到多个相加等于给定数字的数字。在这种情况下，我试图找到 3 个总计目标数字的数字。

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

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

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;

还有。正如我所见，您的数组中有很多重复项，所以我假设允许使用相同的数字，但前提是它是从另一个索引中获取的。在您的循环中，您使用相同的起始索引调用 next 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;
  }
}

使用数字数组相加到特定数字

Using an array of numbers to add up to a specific number

javascript

recursion

jquery

sum

calculation

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