javascript - 如何检查任何数组成员是否可以在 JavaScript 中求和到其中最大的成员？

Question

目标是创建一个函数，该函数将数字数组作为参数，并检查是否可以通过数组中任何其他数字的总和获得其中最大的数字。

一个条件是负数可以是数组的一部分作为参数。

问题

我想出的函数对所有数组成员求和，除了最大的，而不是对它们中的任何一个求和。这就是它失败的原因，如下所示

function ArrayAddition(arr) {
  // Sort small to large
  arr = arr.sort((a, b) => a - b);

  // get maximum number
  var max = arr.pop();
  
  // Sum
  var num = 0;
  arr.forEach((item) => {
    num += item
  });

  return max === num;
}

// Correctly return true
console.log(ArrayAddition([5,7,16,1,3]));

// Wronglly retuns false (5 - 2 + 8 = 11)  
console.log(ArrayAddition([2,5,-2,8,11]));

问题

如果 任何 数组成员加起来最大，我怎样才能让它工作？

Answer 1

从数组中删除最大元素后，任务现在变为给定一个数组和一个目标总和(最大元素)，查找数组中是否存在总和达到目标总和的子序列。此问题与 Subset sum problem 相同

解决这个问题的最简单方法是使用包含排除原则并在 O(2^n) 中解决它，正如 Mihail 的回答已经暗示的那样。还有其他方法可以更有效地解决它(查看子集求和问题链接)

在下面的方法中，我们不生成所有可能的子集，而是只考虑所有这些子集的总和。这将节省大量内存，但最坏的时间复杂度仍然保持不变，即 O(2^n)。

function ArrayAddition(arr) {
  // Sort small to large
  arr = arr.sort((a, b) => a - b);

  // get maximum number
  const max = arr.pop();

  // maintain a set of all possible sums
  const sums = new Set();

  // insert 0 into sums set i.e, sum of an empty set {}
  sums.add(0);

  for (const value of arr) {
    const newSums = new Set();

    for (const sum of sums) {
      // new possible sum if we consider the value in a subset
      const newSum = sum + value;

      // we have a subset whose sum is equal to max
      if (newSum === max)
        return true;

      newSums.add(newSum);
    }

    // insert all new possible sums
    for (const sum of newSums)
      sums.add(sum);
  }

  // no subset which adds up to max was found
  return false;
}

console.log(ArrayAddition([5, 7, 16, 1, 3]));

console.log(ArrayAddition([2, 5, -2, 8, 11]));

举例说明方法

arr = [5,7,16,1,3]

after sorting and removing the max element we have

arr = [1,3,5,7]
max = 16

now initially the set 'sums' only has 0 (empty set)

sums = { 0 }

after the first iteration

sums = {0, 1} which is {[0], [0 +1]}

after the second iteration

sums = {0, 1, 3, 4} which is {[0], [0+1], [0 +3], [0+1 +3]}

after third iteration

sums = {0, 1, 3, 4, 
        5, 6, 8, 9}

after fourth iteration

sums = {0, 1,  3,  4,  5,  6,  8,  9
        7, 8, 10, 11, 12, 13, 15, 16}

since 16 is a possible sum, we return true