使用递归搜索整数数组中元素的所有组合 [英] Using recursion to search all combinations of elements in an array of integers

问题描述

我正在使用JS在Coderbyte上解决此问题:

I am working on this problem from Coderbyte using JS:

让函数ArrayAdditionI(arr)接受存储在arr中的数字数组，如果可以将数组中的任何数字组合加起来等于数组中的最大数字，则返回字符串true，否则返回字符串错误.例如:如果arr包含[4，6，23，10，1，3]，则输出应返回true，因为4 + 6 + 10 + 3 =23.该数组将不会为空，不会包含所有相同的元素，并且可能包含负数.

鉴于需要探索数组元素的各种组合的分支性质，因此对于递归解决方案而言，这个问题似乎已经成熟.我还想使用递归进行一些额外的练习..我还是编码的新手.

The problem seems ripe for a recursive solution, given the branching nature of the need to explore the various combinations of array elements. I would also like to use recursion to get some extra practice.. I'm still very new to coding.

这是我想出的解决方案，在开始测试并发现它根本不是解决方案之前，我对此感到非常高兴:

Here is the solution I came up with, and I was very happy about it until I started testing and discovered that it is not at all a solution:

function ArrayAdditionI(arr) { 
  // sorting the array to easily remove the biggest value
  var sArr = arr.sort(function (a, b) {
    return a-b;});
  // removing the biggest value
  var biggest = sArr.pop();
  // count will be iterated to stop the recursion after the final element of the array has been processed
  var count = 0;
  function recursion (start, i) {
    if (sArr[i] + start === biggest) {
      return true;
    }
    else if (start + sArr[i] < biggest) {
      return recursion(start + sArr[i], i+1);
    }
    else if (start + sArr[i] > biggest && count < sArr.length) {
      count++;
      return recursion(0, count);
    }
    else {
      return false;
    }
  }
  return recursion(0,0);
}

仅当可以加总以满足基本情况的数组元素彼此相邻时，此代码才有效；例如，调用ArrayAdditionI([1,2,3,4])将不起作用，因为必须将这两个元素相加才能达到目标值(位置0为"1"，位置2为"3")不相邻.

This code works only if the array elements which can be summed to fulfill the base case are adjacent to each other; calling ArrayAdditionI([1,2,3,4]), for example, will not work because the two elements which must be summed to reach the target value("1" in position 0, and "3" in position 2) are not adjacent.

我的流程将返回1，然后是1 + 2，然后是1 + 2 + 3，然后是2，然后是2 + 3，然后是3，最后返回 false ，因为目标(4)是还没到.

My flow will return 1, then 1+2, then 1+2+3, then 2, then 2+3, then 3, and finally return false since the target (4) was not reached.

我可以看到适当的解决方案需要如何流过给定的数组，但是我不知道如何通过递归来实现这一点.对于给定的数组[1,2,3,4]，流程应按以下模式检查结果:(位置0，pos0 + pos1，pos0 + pos2，pos0 + pos1 + pos2，pos2，pos2 + pos3，pos3).谁能给我推一下?在一个小时的睡眠中，我将对此作更多的思考，然后在早晨重新尝试一下.也许我的大脑只需要充电即可.

I can visualize how a proper solution needs to flow through a given array, but I don't know how to make this happen through recursion. For the given array [1,2,3,4], the flow should check results in this pattern: (position0, pos0+pos1, pos0+pos2, pos0+pos1+pos2, pos2, pos2+pos3, pos3). Can anyone give me a nudge? I'm going to think on this more before I sleep in an hour and give it a fresh go in the morning.. maybe my brain just needs a recharge.

再次，我真的很陌生，如果我犯了一些非常愚蠢的错误，请告诉我，我会向他们学习.谢谢！

Again, I'm really new to this, if I've made some very silly mistakes please let me know, I'll learn from them. Thanks!

推荐答案

function ArrayAdditionI (arr) {
    var sArr = arr.sort(function (a,b) {
        return a-b;
    });
    var biggest = sArr.pop();
    function recursion (start, indx) {
        if (start + sArr[indx] === biggest) {
            return true;
        }
        else if (sArr.length < indx) {
            return false;
        }
        else if (start + sArr[indx] < biggest) {
            return recursion(start + sArr[indx], indx + 1) || recursion(start, indx+1)
        }
        else {
            return false;
        }
    }
    return recursion(0,0);
}

这篇关于使用递归搜索整数数组中元素的所有组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！