算法 - 查找總和在給定範圍內的子集數

這是一個面試問題。我得到了一系列數字（重複，負數可能）和範圍的下限和上限。我需要找到可能的子集數量，這些子集數將會和範圍內的數字相加。我確實看到了一個特定總和（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

算法 - 查找總和在給定範圍內的子集數

回答

相關問題