JavaScript实现从数组中找和为指定值的唯一数字组合

问题需求 #

编写函数putNum(arrayOfNum: number[], num: number)，从仅包含唯一正整数的数组arrayOfNum中，找出所有和等于num的数字组合，需满足：

• 组合内的数字不能重复使用
• 所有组合必须唯一（不同顺序的同一元素集合视为同一组合）

解决方案 #

这类组合求和问题适合用回溯法解决，结合数组的filter方法预处理数据，优化计算效率。以下是完整实现：

function putNum(arrayOfNum, num) {
    // 过滤掉大于目标值的数，减少无效计算；排序数组，确保组合有序，避免重复组合
    const validNums = arrayOfNum.filter(n => n <= num).sort((a, b) => a - b);
    const result = [];

    // 回溯函数：维护当前路径、当前累加和、遍历起始索引
    const backtrack = (currentPath, currentSum, startIndex) => {
        // 找到符合条件的组合，存入结果
        if (currentSum === num) {
            result.push([...currentPath]);
            return;
        }
        // 累加和超过目标值，直接终止当前分支（剪枝）
        if (currentSum > num) {
            return;
        }

        // 从起始索引开始遍历，避免重复生成同一组合
        for (let i = startIndex; i < validNums.length; i++) {
            currentPath.push(validNums[i]);
            // 递归探索下一个元素，起始索引+1确保不重复使用同一元素
            backtrack(currentPath, currentSum + validNums[i], i + 1);
            // 回溯：移除当前元素，尝试下一个可能
            currentPath.pop();
        }
    };

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

代码说明 #

1. 预处理数组：

   • 用filter过滤掉大于num的元素，因为单个大于目标值的正整数不可能组成符合要求的组合，减少后续遍历次数。
   • 对数组排序，确保生成的组合内元素按升序排列，避免出现[2,3]和[3,2]这类重复组合。

2. 回溯逻辑：

   • 递归函数backtrack负责探索所有可能的组合：
     • 当currentSum等于num时，将当前路径的副本存入结果（避免后续修改影响已保存的组合）。
     • 当currentSum超过num时，直接终止当前分支（剪枝优化，减少不必要的递归）。
     • 从startIndex开始遍历数组，确保每个元素只被使用一次，且不会生成重复组合。

测试用例验证 #

// 测试用例1：目标值远大于数组总和，返回空数组
console.log(putNum([8, 2, 3, 4, 6, 7, 1], 99)); 
// 输出：[]

// 测试用例2：目标值为5
console.log(putNum([8, 2, 3, 4, 6, 7, 1], 5)); 
// 输出：[[1,4],[2,3]]（与示例的[[2,3],[4,1]]为同一组合，仅顺序不同）

// 测试用例3：目标值为8
console.log(putNum([1, 2, 3, 4, 5, 6, 7, 8], 8)); 
// 输出：[[1,2,5],[1,3,4],[1,7],[2,6],[3,5],[8]]（组合正确，顺序不影响唯一性）

关于map/filter/reduce的说明 #

单独使用map（元素转换）、reduce（累积计算）难以处理这类需要遍历所有组合分支的问题，而filter适合用于预处理数据。回溯法是解决这类组合枚举问题的更直接方案，结合数组方法可以优化整体实现。

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