如何优化获取集合元素求和等于目标值的所有唯一组合的JS函数

现有代码存在的问题 #

• 功能局限性：仅支持最多2种不同元素组成的和组合，无法匹配如combinate([2,3,5], 12)中[2,2,2,3,3]这类多元素组合
• 效率缺陷：Array.includes()时间复杂度为O(n)，集合元素较多时调用开销大；每次生成组合后都执行排序，存在冗余计算；未提前过滤大于目标值的无效元素，浪费循环资源
• 输出不稳定：如果输入集合未排序，会生成重复的组合内容

优化实现方案 #

const combinate = (nums, target) => {
  // 预处理：去重、升序排序、过滤大于目标值的无效元素
  const sortedUniqueNums = [...new Set(nums)]
    .sort((a, b) => a - b)
    .filter(num => num <= target)
  const result = []

  // 回溯生成组合：剩余目标值、当前组合、起始搜索下标（避免重复组合）
  const backtrack = (remain, currentComb, start) => {
    if (remain === 0) {
      result.push([...currentComb])
      return
    }
    for (let i = start; i < sortedUniqueNums.length; i++) {
      const num = sortedUniqueNums[i]
      // 剪枝：当前值大于剩余目标值，后续值更大直接跳过
      if (num > remain) break
      currentComb.push(num)
      // 允许重复选取同一元素，所以起始下标保持为i
      backtrack(remain - num, currentComb, i)
      currentComb.pop()
    }
  }

  backtrack(target, [], 0)
  return result
}

优化说明 #

• 功能完备：支持任意数量不同元素组成的合法和组合，覆盖所有需求场景
• 效率提升：预处理阶段提前过滤无效元素，回溯加入剪枝逻辑减少无效分支；通过起始下标控制组合生成顺序，从根源避免重复组合，无需每次生成后排序，也不需要额外判断元素是否存在
• 鲁棒性更强：无论输入集合是否排序、是否存在重复元素，都能输出符合预期的结果

测试调用combinate([2, 3, 5], 8)，返回结果为[[2,2,2,2],[2,3,3],[3,5]]，完全符合预期。

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