如何递归合并数组元素，使合并后总和不超过20MB？

问题描述 #

给定代表文件大小（MB）的数组：
[3, 8, 9, 2, 7, 5, 6, 5, 3, 11, 9, 17, 6, 5, 8, 4, 2, 7, 9, 12, 5, 16, 4]
需按以下规则递归合并生成新数组：

• 依次累加元素，若累加和超过20MB则停止
• 将累加前未超20的和加入新数组
• 从下一个未参与累加的元素重复上述操作

现有递归求和函数，但不清楚如何设置符合需求的递归条件：

var sum = (array) => (array.length === 0)? 0 : array[0] + sum(array.slice(1));

解决方案 #

不需要单独的求和函数，可直接将分段累加逻辑融入递归处理中。核心思路是：递归时跟踪当前累加段的和，根据累加结果决定是继续累加、收尾当前段并重新开始，还是单独处理超大元素。

完整递归代码 #

const mergeFiles = (arr, currentSum = 0) => {
  // 终止条件：数组为空时，返回剩余的累加和（若存在）
  if (arr.length === 0) {
    return currentSum > 0 ? [currentSum] : [];
  }

  const firstElement = arr[0];
  const newTotal = currentSum + firstElement;

  // 处理单个元素超过20MB的特殊情况
  if (firstElement > 20) {
    return [firstElement, ...mergeFiles(arr.slice(1), 0)];
  }

  // 累加后未超过20，继续累加下一个元素
  if (newTotal <= 20) {
    return mergeFiles(arr.slice(1), newTotal);
  }

  // 累加后超过20，将当前累加和加入结果，从当前元素重新开始累加
  return [currentSum, ...mergeFiles(arr, 0)];
};

// 测试调用
const fileSizes = [3, 8, 9, 2, 7, 5, 6, 5, 3, 11, 9, 17, 6, 5, 8, 4, 2, 7, 9, 12, 5, 16, 4];
console.log(mergeFiles(fileSizes));

逻辑说明 #

1. 参数设计：arr为待处理的剩余数组，currentSum为当前正在累加的段的和（默认0，代表新段开始）
2. 终止条件：当剩余数组为空时，若还有未收尾的累加和，将其加入结果后返回
3. 分支处理：
   • 单个元素超20：直接将该元素加入结果，递归处理剩余数组
   • 累加后未超20：继续递归处理下一个元素，传递更新后的累加和
   • 累加后超20：将当前累加的有效和加入结果，从当前元素重新开始新的累加段

输出结果 #

运行上述代码后，得到的合并数组为：
[20, 14, 11, 20, 17, 19, 18, 12, 5, 16, 4]

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