有限FOR LOOP执行过久，JS组合求和算法运行近一天未结束如何优化

原代码运行慢的核心原因 #

原代码本身逻辑没有问题，本质是求解带固定长度约束的子集和问题，运行极慢的核心原因是剪枝条件严重不足，加上有不必要的高开销操作：

• 只做了求和超过目标值的剪枝，完全没用到固定长度room=191的约束做剪枝，大量无效递归分支没有被提前砍掉，比如路径长度已经超过191还在继续递归，或者剩余可选元素全加进来都凑不够191个还在循环。
• 每次找到结果就执行console.log，控制台IO的开销远大于计算逻辑，会拖慢整体执行速度几个数量级。
• 数组元素全为偶数、目标值也为偶数，没有做数值缩放简化计算。

可落地的优化方案 #

1. 补全所有剪枝条件 #

• 路径长度超过room直接终止递归
• 当前路径长度 + 剩余可选元素总数 < room，直接终止当前循环，后续可选元素更少不可能凑够长度
• 剩余需要选k个元素时，提前预判k个元素的最小可能和、最大可能和是否和剩余目标值匹配，不匹配直接剪枝

2. 数值预处理 #

所有元素、目标值统一除以2，数值变小后计算效率更高，最终结果再乘2即可，不影响组合逻辑

3. 移除运行时IO #

去掉所有运行时的console.log输出，只在最终结束后输出统计信息

优化后代码示例 #

let total = 82132 / 2; // 数值缩放为原1/2
let room = 191;
let array = [
  2, 4, 6, 8, 20, 12, 14, 16, 18, 40, 22, 24, 26, 28, 60, 32, 34, 36, 38, 80,
  42, 44, 46, 48, 100, 52, 54, 56, 58, 120, 62, 64, 66, 68, 140, 72, 74, 76, 78,
  160, 82, 84, 86, 88, 180, 92, 94, 96, 98, 200, 102, 104, 106, 108, 220, 112,
  114, 116, 118, 240, 122, 124, 126, 128, 260, 132, 134, 136, 138, 280, 142,
  144, 146, 148, 300, 152, 154, 156, 158, 320, 162, 164, 166, 168, 340, 172,
  174, 176, 178, 360, 182, 184, 186, 188, 380, 192, 194, 196, 198, 400, 202,
  204, 206, 208, 420, 212, 214, 216, 218, 440, 222, 224, 226, 228, 460, 232,
  234, 236, 238, 480, 242, 244, 246, 248, 500, 252, 254, 256, 258, 520, 262,
  264, 266, 268, 540, 272, 274, 276, 278, 560, 282, 284, 286, 288, 580, 292,
  294, 296, 298, 600, 302, 304, 306, 308, 620, 312, 314, 316, 318, 640, 322,
  324, 326, 328, 660, 332, 334, 336, 338, 680, 342, 344, 346, 348, 700, 352,
  354, 356, 358, 720, 362, 364, 366, 368, 740, 372, 374, 376, 378, 760, 382,
  384, 386, 388, 780, 392, 394, 396, 398, 800, 402, 404, 406, 408, 820, 412,
  414, 416, 418, 840, 422, 424, 426, 428, 860, 432, 434, 436, 438, 880, 442,
  444, 446, 448, 900, 452, 454, 456, 458, 920, 462, 464, 466, 468, 940, 472,
  474, 476, 478, 960, 482, 484, 486, 488, 980, 492, 494, 496, 498, 1000, 502,
  504, 506, 508, 1020, 512, 514, 516, 518, 1040, 522, 524, 526, 528, 1060, 532,
  534, 536, 538, 1080, 542, 544, 546, 548, 1100, 552, 554, 556, 558, 1120, 562,
  564, 566, 568, 1140, 572, 574, 576, 578, 1160, 582, 584, 586, 588, 1180, 592,
  594, 596, 598, 1200, 602, 604, 606, 608, 1220, 612, 614, 616, 618, 1240, 622,
  624, 626, 628, 1260, 632, 634, 636, 638, 1280, 642, 644, 646, 648, 1300, 652,
  654, 656, 658, 1320, 662, 664, 666, 668, 1340, 672, 674, 676, 678, 1360, 682,
  684, 686, 688, 1380, 692, 694, 696, 698, 1400, 702, 704, 706, 708, 1420, 712,
  714, 716, 718, 1440,
].map(num => num / 2); // 所有元素缩放为1/2

function allCombinations(arr, target) {
  const result = [];
  const path = [];
  arr.sort((a, b) => a - b);
  const len = arr.length;
  // 预处理后缀和，快速计算剩余k个元素的最小和
  const suffixSum = new Array(len + 1).fill(0);
  for (let i = len - 1; i >= 0; i--) {
    suffixSum[i] = suffixSum[i + 1] + arr[i];
  }

  function helper(sum, startIndex) {
    const pathLen = path.length;
    // 长度超过直接返回
    if (pathLen > room) return;
    // 长度刚好匹配时校验和
    if (pathLen === room) {
      sum === target && result.push(path.map(num => num * 2));
      return;
    }
    const need = room - pathLen;
    // 剩余元素不够凑够need个，直接结束
    if (startIndex + need > len) return;
    // 剩余最小和超过目标，剪枝
    const minRemainSum = sum + suffixSum[startIndex] - suffixSum[startIndex + need];
    if (minRemainSum > target) return;
    // 剩余最大和小于目标，剪枝
    const maxRemainSum = sum + suffixSum[len - need];
    if (maxRemainSum < target) return;

    for (let i = startIndex; i < len && sum + arr[i] <= target; i++) {
      if (i > startIndex && arr[i] === arr[i - 1]) continue;
      path.push(arr[i]);
      helper(sum + arr[i], i + 1);
      path.pop();
    }
  }
  helper(0, 0);
  return result;
}
const result = allCombinations(array, total);

如果你的场景不需要输出所有组合，只需要验证是否存在或者取少量结果，可以在找到第一个符合条件的组合之后就直接终止所有递归，速度会进一步大幅提升。

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