JavaScript（Google表格脚本）中求解和为给定值的三元组所有组合（星条/球盒问题）

核心实现逻辑 #

• 问题本质为球盒模型的典型应用：将给定的目标总和值作为“待分配的球”，将三元组的三个位置作为固定顺序的“盒子”，枚举所有满足三数之和等于目标值的组合，通过非降序约束彻底避免排列重复
• 代码完全适配Google表格脚本编辑器的运行环境，无外部依赖，粘贴即可直接使用
• 支持自定义参数：可配置是否允许三元组包含0值、输出去重后的无重复组合

可直接复用的代码 #

/**
 * 生成所有和为指定值的无重复三元组组合
 * @param {number} targetSum 目标总和数值
 * @param {boolean} [allowZero=false] 是否允许三元组包含0值，默认仅返回正整数组合
 * @returns {Array<Array<number>>} 符合条件的三元组集合
 */
function getSumTriples(targetSum, allowZero = false) {
  const result = [];
  const startVal = allowZero ? 0 : 1;
  // 第一层循环锁定第一个数，通过范围裁剪减少无意义遍历
  for (let a = startVal; a <= targetSum / 3; a++) {
    // 第二层循环锁定第二个数，保证b >= a 避免重复排列
    const bLowerBound = a;
    const bUpperBound = (targetSum - a) / 2;
    for (let b = bLowerBound; b <= bUpperBound; b++) {
      const c = targetSum - a - b;
      // 严格按非降序[a, b, c]存储，从根源上消除组合重复
      result.push([a, b, c]);
    }
  }
  return result;
}

// 表格自定义函数入口，可直接在单元格内调用
function GET_SUM_TRIPLES(targetSum, allowZero) {
  return getSumTriples(targetSum, allowZero);
}

实际使用方法 #

• 打开Google表格，进入「扩展程序」-「Apps Script」编辑器，删除编辑器内原有示例代码，粘贴上述代码后保存项目即可
• 表格内调用规则：
  • 输入=GET_SUM_TRIPLES(10)，即可返回所有和为10的正整数三元组：[1,1,8]、[1,2,7]、[1,3,6]、[1,4,5]、[2,2,6]、[2,3,5]、[2,4,4]、[3,3,4]
  • 如果需要允许0值参与组合，调用时补充第二个参数为TRUE，例如=GET_SUM_TRIPLES(5, TRUE)即可生成包含0的合法组合

效果说明 #

• 枚举数量和星条法的理论计数完全匹配：允许非负整数时，n的三元组组合数为(n+2)(n+1)/2；要求正整数时，组合数为(n-1)(n-2)/2，不存在漏算或多算
• 所有语法均兼容Google Apps Script的运行规范，不会出现语法报错或权限问题

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