从给定数字中查找总和≤指定值的所有5元素组合

通用场景规则 #

• 适用范围：从任意规模的数字集合中，查找所有元素个数固定为5、元素总和不超过预设阈值的组合
• 核心约束：筛选结果为无重复的无序组合，不会因元素排列顺序不同生成冗余结果
• 效率优化核心：生成组合时固定元素的选取顺序（后选取元素的索引必须大于前一次选取的元素索引），从根源上消除重复组合，避免无效计算

特定场景落地（20个数字、阈值100） #

• 前置处理：将待筛选的20个数字按数值做升序排序，为剪枝优化提供基础
• 分支剪枝逻辑：
  • 生成组合过程中，若当前累计的元素和已经超过100，直接终止当前分支的后续选取：因为数组升序排列，后续选取的元素数值只会更大，该分支下所有待生成的组合都不可能满足阈值要求
  • 若剩余可选取的数字数量，不足以凑满组合要求的5个元素，直接终止当前分支
• 结果汇总：当组合元素数凑满5个且最终总和≤100时，将该组合纳入有效结果集

# 核心逻辑参考实现（输入：待筛选数字列表input_nums，阈值max_total=100）
input_nums.sort()
valid_groups = []
def generate_group(start_index, current_group, current_sum):
    # 凑满5个元素时校验总和
    if len(current_group) == 5:
        if current_sum <= max_total:
            valid_groups.append(current_group.copy())
        return
    # 剩余可选元素不足时提前终止
    if 5 - len(current_group) > len(input_nums) - start_index:
        return
    for idx in range(start_index, len(input_nums)):
        # 当前元素加入就超阈值，后续元素更大，直接跳出循环
        if current_sum + input_nums[idx] > max_total:
            break
        current_group.append(input_nums[idx])
        generate_group(idx + 1, current_group, current_sum + input_nums[idx])
        current_group.pop()
generate_group(0, [], 0)

实现说明：如果原始数字集合中存在重复值，可根据业务需求决定是否对重复数值做去重处理，避免生成数值完全一致的重复组合。

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