使用递归搜索整数数组中元素的所有组合

Question

我正在使用 JS 从 Coderbyte 解决这个问题：

让函数 ArrayAdditionI(arr) 获取存储在 arr 中的数字数组和 return 字符串，如果数组中的任何数字组合相加等于最大的数组中的数字，否则 return 字符串 false。例如：如果 arr 包含 [4, 6, 23, 10, 1, 3] 输出应该 return true 因为 4 + 6 + 10 + 3 = 23。数组不会为空，不会包含所有相同的元素，并且可能包含负数。

鉴于需要探索数组元素的各种组合的分支性质，递归解决方案的问题似乎已经成熟。我还想使用递归来获得一些额外的练习。我对编码还是很陌生。

这是我想出的解决方案，我对此感到非常高兴，直到我开始测试并发现它根本不是一个解决方案：

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”）是不相邻。

我的流程会return1，然后是1+2，然后是1+2+3，然后是2，然后是2+3，然后是3，最后是return false 因为没有达到目标 (4)。

我可以想象一个正确的解决方案需要如何流经给定的数组，但我不知道如何通过递归实现这一点。对于给定的数组 [1,2,3,4]，流程应按以下模式检查结果：(position0, pos0+pos1, pos0+pos2, pos0+pos1+pos2, pos2, pos2+pos3, pos3)。谁能给我一个微调？我会在一个小时后睡觉前多考虑一下，然后在早上重新开始。也许我的大脑需要充电。

再说一次，我真的很陌生，如果我犯了一些非常愚蠢的错误，请告诉我，我会从中吸取教训。谢谢！

Answer 1

你的算法有缺陷。您的功能看起来只向前迈进了一步。您需要在内部添加循环以查看所有剩余值。

function ArrayAdditionI(arr) {
    // sorting the array to easily remove the biggest value
    // slice added to prevent original array modification
    var sArr = arr.slice().sort(function (a, b) { 
        return a - b;
    });
    // removing the biggest value
    var biggest = sArr.pop();
    function recursion(start, i) {
        var result = false;
        // looking over all rest values of array
        for (var j = i; j < sArr.length && !result; j++) {
            if (sArr[j] + start === biggest) {
                result = true;
            }
            else if (start + sArr[j] < biggest) {
                result = recursion(start + sArr[j], j + 1);
            }
        }
        return result;
    }
    return recursion(0, 0);
}

Answer 2

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);
}

使用递归搜索整数数组中元素的所有组合

Using recursion to search all combinations of elements in an array of integers

javascript

arrays

recursion

combinations