如何修改JavaScript函数，实现检查数组任意元素之和等于最大值？

原函数的问题在于仅计算了所有剩余元素的总和，而非任意数量元素的组合之和。要解决这个问题，我们需要检查是否存在一个元素子集（非空、任意数量），其和等于数组的最大值。由于数组允许包含负数，我们需要使用能覆盖正负数值的子集和求解方法。

方案1：迭代集合法（高效覆盖所有可能和） #

通过维护一个集合来记录所有可能的子集和，逐步迭代每个元素并扩展可能的和集合：

function ArrayAddition(arr) {
  // 排序后取出最大值
  arr.sort((a, b) => a - b);
  const max = arr.pop();
  
  // 初始化集合，包含空子集的和0
  let possibleSums = new Set([0]);
  
  for (const num of arr) {
    // 基于现有和生成新的可能和（加入当前元素后的结果）
    const newSums = [...possibleSums].map(sum => sum + num);
    // 将新和合并到集合中
    newSums.forEach(sum => possibleSums.add(sum));
    
    // 提前终止：如果已找到目标值，直接返回true
    if (possibleSums.has(max)) {
      return true;
    }
  }
  
  return possibleSums.has(max);
}

// 测试用例
console.log(ArrayAddition([5,7,16,1,3])); // true
console.log(ArrayAddition([2,5,-2,8,11])); // true

方案2：递归回溯法（代码简洁直观） #

通过递归遍历每个元素的“选/不选”两种情况，检查是否能凑出目标最大值：

function ArrayAddition(arr) {
  arr.sort((a, b) => a - b);
  const max = arr.pop();
  
  // 递归检查：从index位置开始，能否凑出target
  const canReachTarget = (target, index) => {
    if (target === 0) return true;
    if (index >= arr.length) return false;
    // 两种选择：选当前元素，或不选当前元素
    return canReachTarget(target - arr[index], index + 1) || canReachTarget(target, index + 1);
  };
  
  return canReachTarget(max, 0);
}

// 测试用例
console.log(ArrayAddition([5,7,16,1,3])); // true
console.log(ArrayAddition([2,5,-2,8,11])); // true

方案说明 #

• 集合法：通过迭代扩展可能的和集合，能有效处理包含负数的场景，且避免递归栈溢出问题，适合元素较多的数组。
• 递归法：代码逻辑直观易懂，但当数组长度过大时，可能触发递归深度限制，可考虑添加记忆化优化进一步提升性能。

内容的提问来源于stack exchange，提问作者Razvan Zamfir