如何快速找出数字列表中首个和为指定值的组合？

给定一组数字列表，需找出其中首个和为指定目标值的数字组合（示例：列表[1,2,3,4,5]，目标值5，可返回[1,4]或[2,3]），核心要求是尽可能快速得到符合条件的组合。

尝试用Python的itertools.combinations实现，但运行耗时过长，代码如下：

from typing import List
import itertools

def test(target_sum, numbers):
    for i in range(len(numbers), 0, -1):
        for seq in itertools.combinations(numbers, i):
            if(sum(seq) == target_sum):
                return seq


if __name__ == "__main__":
    target_sum: int = 616
    numbers: List[int] = [16, 96, 16, 32, 16, 4, 4, 32, 32, 10, 16, 8, 32, 8, 4, 16, 8, 8, 8, 16, 8, 8, 8, 16, 8, 16, 16, 4, 8, 8, 16, 12, 16, 16, 8, 16, 8, 8, 8, 8, 4, 32, 16, 8, 32, 16, 8, 8, 8, 8, 16, 32, 8, 32, 8, 8, 16, 24, 32, 8]

    print(test(target_sum, numbers))

你的代码效率低下的原因主要有两点：

1. 从最长组合开始遍历，而组合数随长度变化呈先增后减的趋势，大长度组合的遍历计算量极大；
2. itertools.combinations会生成所有可能的组合，没有任何剪枝逻辑，完全依赖暴力枚举，当列表元素较多时，时间复杂度会指数级上升。

下面提供两种高效的实现思路，可根据你的具体需求选择：

思路1：回溯+剪枝（优先找含大元素的组合） #

先将数组降序排序，通过回溯法遍历可能的组合，同时加入剪枝逻辑，提前排除不可能达到目标和的路径，大幅减少计算量。如果需要优先找到包含大元素的组合，这个方法很合适。

from typing import List

def find_combination(target_sum: int, numbers: List[int]) -> List[int]:
    sorted_nums = sorted(numbers, reverse=True)
    n = len(sorted_nums)

    for length in range(1, n + 1):
        # 剪枝：当前长度下最大元素和仍小于目标，直接跳过
        if sum(sorted_nums[:length]) < target_sum:
            continue
        # 剪枝：当前长度下最小元素和已大于目标，后续更长组合无需再看
        if sum(sorted_nums[-length:]) > target_sum:
            break

        # 回溯寻找当前长度的有效组合
        def backtrack(start: int, path: List[int], current_sum: int):
            if len(path) == length:
                return path.copy() if current_sum == target_sum else None
            for i in range(start, n):
                remaining = length - len(path) - 1
                # 剪枝：当前路径+当前元素+剩余所需最小元素总和超过目标，跳过
                min_remaining_sum = sum(sorted_nums[i+1:i+1+remaining]) if remaining > 0 else 0
                if current_sum + sorted_nums[i] + min_remaining_sum > target_sum:
                    continue
                # 剪枝：当前路径+当前元素已超过目标，跳过（降序排列，后续元素更小，无需继续）
                if current_sum + sorted_nums[i] > target_sum:
                    continue
                path.append(sorted_nums[i])
                result = backtrack(i + 1, path, current_sum + sorted_nums[i])
                if result:
                    return result
                path.pop()
            return None

        result = backtrack(0, [], 0)
        if result:
            return result
    return []

if __name__ == "__main__":
    target_sum: int = 616
    numbers: List[int] = [16, 96, 16, 32, 16, 4, 4, 32, 32, 10, 16, 8, 32, 8, 4, 16, 8, 8, 8, 16, 8, 8, 8, 16, 8, 16, 16, 4, 8, 8, 16, 12, 16, 16, 8, 16, 8, 8, 8, 8, 4, 32, 16, 8, 32, 16, 8, 8, 8, 8, 16, 32, 8, 32, 8, 8, 16, 24, 32, 8]
    print(find_combination(target_sum, numbers))

思路2：动态规划（优先找遍历顺序中最早出现的组合） #

用动态规划记录每个可能的和对应的组合，遍历每个数字时更新dp表，一旦找到目标和就立即返回对应的组合。这个方法效率极高，且返回的是按原列表遍历顺序找到的第一个有效组合。

from typing import List, Dict

def find_combination_dp(target_sum: int, numbers: List[int]) -> List[int]:
    # dp[s] 存储和为s的一个组合
    dp: Dict[int, List[int]] = {0: []}

    for num in numbers:
        # 逆序遍历避免重复使用同一元素（若允许重复使用可改为正序）
        for s in list(dp.keys()):
            new_sum = s + num
            if new_sum == target_sum:
                return dp[s] + [num]
            if new_sum < target_sum and new_sum not in dp:
                dp[new_sum] = dp[s] + [num]
    return []

if __name__ == "__main__":
    target_sum: int = 616
    numbers: List[int] = [16, 96, 16, 32, 16, 4, 4, 32, 32, 10, 16, 8, 32, 8, 4, 16, 8, 8, 8, 16, 8, 8, 8, 16, 8, 16, 16, 4, 8, 8, 16, 12, 16, 16, 8, 16, 8, 8, 8, 8, 4, 32, 16, 8, 32, 16, 8, 8, 8, 8, 16, 32, 8, 32, 8, 8, 16, 24, 32, 8]
    print(find_combination_dp(target_sum, numbers))

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