高效生成无冗余超阈值N整数子集的算法优化咨询

需要设计高效的整数集合子集生成方案，生成的所有子集需满足元素和超过指定阈值N，且子集中不包含任何冗余成员。
约束规则：

• 若某一子集的元素和已经超过N，不得再向该子集添加额外元素
• 所有满足和超N的合法子集，不得作为其他更大子集的子集出现，即合法子集是极小的和超阈值子集：去掉子集中任意一个元素后，元素和将小于等于N。

给定测试整数集合：
[1, 2, 5, 1, 3]
当阈值N = 6时，符合要求的结果为：
[5, 2] [5, 1, 1] [5, 3] [3, 2, 1, 1]
以上所有子集均不存在冗余成员。例如[5, 2, 1]不属于合法结果，因为[5, 2]的和已经超过N，任何包含[5,2]作为子集的更大集合均为冗余结果。

原有代码可生成所有和超过阈值N的子集，但未过滤冗余结果，实现如下：

from collections import Counter

def solve(nums, target):
    counts = sorted(Counter(nums).items())
    reserve = sum(nums) - target
    
    if reserve <= 0:
        return []
    return list(_solve(counts, reserve, []))

def _solve(counts, reserve, prefix):
    if not counts:
        yield tuple(prefix)
        return
    
    val, max_count = last = counts.pop()
    
    prefix.extend([val] * max_count)
    yield from _solve(counts, reserve, prefix)
    
    for count in range(1, max_count + 1):
        prefix.pop()
        if reserve - count * val > 0:
            yield from _solve(counts, reserve - count * val, prefix)
    
    counts.append(last)

原有代码采用补集思路：合法子集S满足sum(S) > N等价于其补集T（全集减S）满足sum(T) < sum(nums) - N = reserve。要求S无冗余，等价于要求T是极大的满足和小于reserve的子集：即T无法再添加任何剩余元素，否则和将大于等于reserve。
只需在原有递归逻辑中增加极大性判断，提前终止无效递归即可，无需枚举所有子集再过滤，效率很高。修改后的完整代码如下：

from collections import Counter

def solve(nums, target):
    total = sum(nums)
    reserve = total - target
    if reserve <= 0:
        return []
    counts = sorted(Counter(nums).items())
    result = []
    total_cnt = Counter(nums)
    for t in _solve(counts, reserve, []):
        # t是补集（不选的元素），构造选出来的合法子集
        cnt = Counter(t)
        subset = []
        for num, c in total_cnt.items():
            subset.extend([num] * (c - cnt.get(num, 0)))
        result.append(tuple(sorted(subset, reverse=True)))
    return result

def _solve(counts, reserve, prefix):
    # 终止条件：没有剩余元素，或者剩余最小元素加入补集后就超过reserve上限，说明当前补集是极大的
    if not counts or counts[0][0] >= reserve:
        yield tuple(prefix)
        return
    
    val, max_count = last = counts.pop()
    # 从多到少尝试选多少个当前元素放入补集（即不选多少个当前元素）
    for cnt in range(max_count, -1, -1):
        cost = cnt * val
        if cost >= reserve:
            continue  # 放cnt个就超补集和上限，跳过
        prefix.extend([val] * cnt)
        yield from _solve(counts, reserve - cost, prefix)
        # 回溯
        if cnt > 0:
            del prefix[-cnt:]
    
    counts.append(last)

代码修改点说明：

• 调整补集元素的选取循环，从全选当前元素放入补集开始逐次减少，跳过所有会让补集和超过reserve的无效分支
• 新增极大性判断：当剩余最小元素的值大于等于补集剩余可用额度时，说明补集已经无法再加入任何元素，直接返回结果，不再继续递归生成更小的补集（对应冗余的超长子集）
• 补集递归完成后，将补集转换为对应的目标子集格式返回，和示例输出格式对齐

测试上述代码，输入[1,2,5,1,3]、阈值6时，返回结果为[(5,2), (5,1,1), (5,3), (3,2,1,1)]，完全符合要求。

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