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

Question

首先，让我说我找到了许多问题和答案，这些问题和答案似乎有些相关或与这个问题有些相关，但实际上并不是这个问题。它似乎与硬币变更 /子集总和问题有关，但是我认为这完全不同，子集总和答案不涵盖这个问题。

问题

是说我有一组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 的第一组时，可以说 g ₁ ，您也可以立即添加所有包含 g的所有其他集合 ₁ 作为子集。同样，如果您找到了另一个新集 g ₂ 尚未添加并且也超过 n ，则可以立即添加所有包含<的集合强> g ₂ 作为子集。您无需检查这些集合是否总和大于 n 。

如果您总结了 s 的所有成员，并且结果不大于 n ，那么您可以得出结论，没有符合标准的集合。

实际用例

在这里试图实现的现实世界目标是我有一组具有与之相关的数值的项目，而另一个代表阈值的值。我试图找出是否可以例行地找到所有可以超过阈值的子组的子群，当它们的权重求和时。

生成符合此标准的所有集合的最有效方法是什么？这是什么复杂性？

Answer 1

这是一个更有效的实施。值得注意的说明：

• 它正确处理重复的元素以避免返回相同的子集
• 实际上两次，它通过将同价值的元素分组为带有数量的垃圾箱，
• 从而避免完全重新计算等效的子集在保持阈值之上和早期外观的同时，以避免完全探索较小的子集，
• 它使用列表突变来避免使用昂贵的列表创建 /应对，直到绝对必要时
• 它确实使用递归，因此在那里有少量的性能罚款，并且与所有递归一样：如果您向其投入足够大的输入，它会引起错误。如果成为问题的问题，则是对读者进行练习，以将其移植到迭代变体中

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

意味着它可以解决25个元素的问题，其中解决方案包含约225毫秒的〜100K不同的子集。

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

关于时间复杂性，很难绑定它，因为它的运行时间确实取决于数字的值（或者是输出大小）。您可以将其绑定为o（n log n + s * n）其中n是输入列表的大小，s是输出列表的大小。

Answer 2

您可以使用itertools生成子列表，然后根据条件过滤这些列表：

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)

时间复杂性很高，因为您首先需要生成每个长度的子清单（外部循环），然后根据条件（内部的循环）搜索正确的值，因此至少是O（n^2）。