算法 - 查找总和在给定范围内的子集数

这是一个面试问题。我得到了一系列数字（重复，负数可能）和范围的下限和上限。我需要找到可能的子集数量，这些子集数将会和范围内的数字相加。我确实看到了一个特定总和（find all subsets that sum to a particular value）的问题，但我不认为为范围内的每个数字做这件事是最有效的。算法 - 查找总和在给定范围内的子集数

范围可以从-10^7到10^7。

来源

2016-12-27 Bharg

这似乎是你连接到的答案可以适应。你可能已经给了它一些想法，但是你没有描述你的问题，因此除了编写解决方案之外，很难提供有用的帮助。 –

这显然是NP难。动态编程方法是很自然的。 –

这个问题至少与子集总和问题一样困难，但是当权重总和有界时，我不知道它是否仍然是np-hard或变得易于处理。 –

子集总和的经典DP可以修改来解决这个问题，保持一个计数而不是布尔指标是否存在给定和的解。

def subset_sum_count(lst, a, b): 
    sum_count = collections.Counter({0: 1}) 
    for x in lst: 
     for s, c in list(sum_count.items()): 
      sum_count[s + x] += c 
    return sum(c for (s, c) in sum_counts.items() if a <= s <= b)

来源

2016-12-27 18:27:07

算法 - 查找总和在给定范围内的子集数

回答

相关问题