如何使用JavaScript查找数组中所有和为28的不重复元素组合

你需要实现的是典型的无重复元素子集和求解，使用回溯算法即可完成，核心逻辑是遍历元素时仅向后递归，避免重复调用同位置元素，同时加入剪枝逻辑减少不必要的计算。

完整可运行代码 #

const array = [2,4,6,8,20,12,14,16,18,40]
const target = 28
const result = []

// 回溯参数：遍历起始索引、剩余需要凑的数值、当前已选组合
function backtrack(startIndex, remainValue, currentGroup) {
    // 剩余数值为0，说明当前组合符合要求，存入结果
    if (remainValue === 0) {
        result.push([...currentGroup])
        return
    }
    // 剩余数值小于0或已经遍历完所有元素，直接终止当前分支
    if (remainValue < 0 || startIndex >= array.length) return

    for (let i = startIndex; i < array.length; i++) {
        // 剪枝：当前元素已经大于剩余需要凑的数值，直接跳过
        if (array[i] > remainValue) continue
        // 选中当前元素
        currentGroup.push(array[i])
        // 递归处理下一个元素，i+1保证不会重复使用当前位置的元素
        backtrack(i + 1, remainValue - array[i], currentGroup)
        // 回溯：撤销对当前元素的选择
        currentGroup.pop()
    }
}

backtrack(0, target, [])
// 打印所有符合要求的组合
console.log(result)

输出结果 #

运行上述代码，得到的所有符合条件的组合如下：

[
  [2,4,6,16],
  [2,4,8,14],
  [2,6,8,12],
  [2,6,20],
  [2,8,18],
  [2,12,14],
  [4,6,18],
  [4,8,16],
  [6,8,14],
  [8,20],
  [12,16]
]

如果提前对数组做升序排序，还可以进一步优化剪枝逻辑，当前元素大于剩余值时直接终止当前循环，减少遍历次数。

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