最优解需求：从指定列表选1-10个可重复元素求和等于目标值

思路 #

要实现速度优先的解决方案，我们不需要枚举所有可能的组合，只需找到第一个符合条件的结果即可。核心优化点如下：

• 优先选大元素：将数组反转成降序，优先尝试大数值元素，快速缩小目标值target，减少所需元素数量，同时满足最多选10个的限制。
• 提前边界过滤：直接排除不可能的场景，比如target小于数组最小元素（1），或大于10个最大元素的总和（10*6498=64980），直接返回undefined。
• 剪枝优化：遍历过程中跳过无效分支：
  • 当前元素大于剩余目标值时直接跳过；
  • 若剩余可用位置全选当前元素仍凑不够剩余目标值，直接跳过后续更小元素（降序排列，更小元素更无法满足）。
• 立即返回结果：一旦找到符合条件的组合，立即终止计算并返回，避免不必要的遍历。

实现代码 #

const list = [
    1,
    3,
    6,
    8,
    12,
    18,
    25,
    28,
    30,
    40,
    45,
    50,
    60,
    68,
    78,
    88,
    98,
    128,
    158,
    198,
    248,
    298,
    348,
    418,
    488,
    548,
    588,
    618,
    648,
    698,
    798,
    818,
    848,
    898,
    998,
    1048,
    1098,
    1148,
    1198,
    1248,
    1298,
    1398,
    1448,
    1498,
    1598,
    1648,
    1998,
    2298,
    2598,
    2998,
    3298,
    3998,
    4498,
    4998,
    5898,
    6498,
];

// 预处理：转为降序数组，优先尝试大元素
const sortedDescList = [...list].reverse();

function getCombinations(
    list: number[],
    target: number
): Array<number> | undefined {
    const minVal = list[list.length - 1];
    const maxVal = list[0];
    // 边界情况快速过滤
    if (target < minVal || target > 10 * maxVal) {
        return undefined;
    }

    // 回溯函数：剩余目标值、已选元素、当前遍历起始索引
    const backtrack = (remainingTarget: number, path: number[], startIndex: number): number[] | undefined => {
        // 找到有效组合：和为target，元素数量1-10
        if (remainingTarget === 0) {
            if (path.length >= 1 && path.length <= 10) {
                return path;
            }
            return undefined;
        }
        // 元素数量超过10，直接剪枝
        if (path.length >= 10) {
            return undefined;
        }

        for (let i = startIndex; i < sortedDescList.length; i++) {
            const num = sortedDescList[i];
            // 当前元素大于剩余目标值，跳过（降序排列，后续更小无需遍历）
            if (num > remainingTarget) {
                continue;
            }
            // 剪枝：剩余位置全选当前元素也凑不够目标值，跳过
            const remainingSlots = 10 - path.length;
            if (num * remainingSlots < remainingTarget) {
                continue;
            }

            // 选择当前元素，继续回溯
            const result = backtrack(remainingTarget - num, [...path, num], i);
            // 找到结果立即返回，终止递归
            if (result) {
                return result;
            }
        }

        return undefined;
    };

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

测试示例 #

console.log(getCombinations(list, 10)); // 输出 [8,1,1]（或其他有效组合）
console.log(getCombinations(list, 20)); // 输出 [18,1,1] 或 [12,8]
console.log(getCombinations(list, 0)); // 输出 undefined
console.log(getCombinations(list, 100000)); // 输出 undefined

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