对于一组整数，获取总和大于某个值的所有集合

Question

首先我要说的是，我发现很多问题和答案都回答了一些看似相关或接近这个问题，但实际上不是这个问题的问题。这似乎与硬币找零/子集总和问题有关，但我认为这明显不同，以至于子集总和答案不涵盖这个问题。

问题

假设我有一组 4 个整数，称为 S：[1, 2, 5, 1]

目标是设计一组集合 G ，它由 S 的每个子集组成，其中set 大于某个值 N.

在此示例中，如果 N = 6，则 G 将是 [ [5,2,1,1], [5,2,1], [5,2], [5,1,1] ]

注意事项

我这里特地选了set这个词，因为每组的顺序根本不重要。 [5, 2, 1, 1] 等同于 [5, 1, 1, 2].

当您创建第一个超过 N 的集时，假设 G₁，您还可以立即添加包含 G₁ 的所有其他集合作为子集。同样，如果你发现另一个新的集合G₂，它还没有添加并且也超过了N，您可以立即添加所有包含 G₂ 的集合作为子集。您不需要检查这些集合的总和是否大于 N.

如果对S的所有成员求和且结果不大于N，则可以断定不存在集合符合条件。

实际用例

这里要实现的现实目标是我有一组项目，这些项目具有与之关联的数值权重，以及另一个代表阈值的值。我正在尝试找出当它们的权重相加时，是否可以例行地找到可以由超过阈值的项目组成的所有子组。

生成满足此条件的所有集合的最有效方法是什么？这个的复杂度是多少？

Answer 1

您可以使用 itertools 生成 sub-lists，然后根据条件筛选这些列表：

import itertools

input_list = [1, 2, 5, 1]
threshold = 6

result = []

for length in range(len(input_list) + 1):

    search_space = list(itertools.combinations(input_list, length))

    for item in search_space:
        if sum(item) > threshold:
            result.append(item)

print(result)

时间复杂度很高，首先需要生成每个长度的sub-lists（外层for循环），然后根据条件搜索正确的值（内层for循环），所以至少是O (n^2).

Answer 2

这是一个更高效的实现。值得注意的是：

它正确地处理了重复的元素以避免返回相同的子集两次
事实上，它通过将 same-valued 个元素分组到具有计数
它从最大的子集（集合本身）开始，在保持在阈值以上的同时逐渐删除元素，early-exits以避免完全探索较小的子集
它使用列表变异来避免昂贵的列表创建/处理，直到绝对必要
它确实使用了递归，所以这里有一个小的性能损失，并且与所有递归一样：如果你向它抛出足够大的输入，它会引发错误。这是对 reader 的一个练习，如果这成为一个问题

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)

计时：

from timeit import timeit

runs = 10
statement = "solve([randrange(15) for _ in range(25)], 100)"
setup = "from __main__ import solve; from random import randrange"
print(timeit(statement, setup=setup, number=runs)/runs)

输出：

0.22455865999218078

这意味着它能够在大约 225 毫秒内解决 25 个元素的问题，其中解决方案包含约 100k 个不同的子集。

我确实针对天真的解决方案对此进行了测试，以确保正确性。

关于时间复杂度，很难对此进行限制，因为它的运行时间实际上取决于数字的值（或者更确切地说，输出大小）。您可以将其绑定为 O(n log n + s * n)，其中 n 是输入列表的大小，s 是输出列表的大小。

对于一组整数，获取总和大于某个值的所有集合

For a Set of Integers, Get All Sets Whose Sum is Greater Than Some Value

set

permutation

subset-sum