查找整数集合中所有和大于指定阈值的子集的高效算法

我查阅过大量看似与本问题相关的问答内容，但均未直接解答本问题。本问题看似与硬币找零、子集和问题相关，但二者存在明显差异，现有子集和问题的解决方案无法直接覆盖本场景。

给定包含4个整数的集合S：[1, 2, 5, 1]，目标是构造集合的集合G，其中包含S所有元素和大于指定阈值N的子集。
在本示例中，若取N = 6，则符合要求的结果集G为[ [5,2,1,1], [5,2,1], [5,2], [5,1,1] ]。

• 子集内元素顺序不影响结果判定，例如[5, 2, 1, 1]与[5, 1, 1, 2]视为完全相同的子集。
• 若找到任意和大于N的子集，则所有包含该子集作为子集的超集可直接加入结果集，无需重复校验其和是否满足要求。
• 若集合S的所有元素总和不大于N，则可直接判定不存在符合要求的子集。

我有一批带有数值权重属性的物品，以及一个固定权重阈值，需要判断是否可以常态化高效计算所有权重和超过阈值的物品子组合。

生成所有符合上述要求的子集的最高效实现方法是什么？该算法的时间复杂度为多少？

最高效实现方法 #

最适配该场景的方案是降序排序+剪枝回溯，配合最小命中子集批量生成规则，是当前计算量最小的实现思路，具体流程如下：

1. 前置预处理：先把集合内元素按数值从大到小排序，同时统计所有元素的总和，如果总和不超过N，直接返回空结果即可。排序的核心作用是优先选择权重大的元素，更早凑够超过阈值的和，最大化剪枝收益。比如示例中的集合排序后为[5,2,1,1]。
2. 回溯搜索最小满足条件的子集：按排序后的顺序递归遍历，每一步决定选或不选当前元素，同时维护当前已选元素的和值：
   • 如果当前已选元素的和已经大于N，不需要继续向下递归选择后续元素——因为无论后续元素选或不选，得到的都是当前集合的超集，全部符合要求，直接将剩余未处理元素做任意选/不选的组合，和当前已选元素拼接后直接加入结果集即可，不需要重复计算和值校验。
   • 增加无效分支剪枝：如果当前已选元素的和加上剩余所有未遍历元素的和仍然不大于N，直接剪掉当前分支，不需要继续向下搜索，不可能产出符合要求的结果。
   • 去重处理：排序后相同值的元素是相邻的，如果当前元素和上一个元素值相同，且上一个元素没有被选中，说明当前分支已经在上一个元素的递归逻辑中覆盖过，直接跳过即可，避免生成重复子集。比如示例中的两个1，不会出现“选第一个1不选第二个”和“选第二个1不选第一个”生成重复结果的问题。

以示例N=6的场景跑一遍流程即可验证逻辑正确性：

• 第一步选5，当前和为5<6，继续向下递归
• 第二步选2，当前和为7>6，命中阈值，后续两个1可任意选择，直接生成[5,2]、[5,2,1]、[5,2,1,1]三个结果，回溯到上一层
• 第二步不选2，当前和为5，继续向下选第一个1，和为6不满足大于阈值的要求，再选第二个1，和为7>6，命中阈值，生成[5,1,1]，回溯到上一层
• 第一步不选5，剩余所有元素总和为4<6，直接剪掉整个分支，不需要继续遍历，最终得到的结果和示例完全一致。

时间复杂度 #

• 最坏场景为阈值N接近0，几乎所有子集都满足要求，此时时间复杂度为O(2^k)，k为集合去重后的元素个数，和生成所有子集的基础复杂度一致，但因为存在剪枝逻辑，实际运行速度远快于暴力枚举所有子集再逐一校验和值的方案。
• 绝大多数实际业务场景下，尤其是常态化计算的场景，阈值通常接近集合元素总和，满足要求的子集占比不高，此时依托大元素优先搜索、超集批量生成、无效分支剪枝的优化，实际运行复杂度远低于O(2^k)，只需要找到少量最小满足条件的子集即可批量生成全部结果，性能完全满足高频计算要求。
• 如果集合中存在大量重复元素，还可以基于多重集合的组合生成逻辑进一步优化，时间复杂度还会继续降低。

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