找到列表中哪些数字的和等于某个值的算法

Question

我有一串数字，还有一个特定的和。这个和是由我列表中的几个数字加起来的（我可能知道也可能不知道是几个数字加起来的）。有没有什么快速的方法可以找出可能的数字组合？如果能用Python写就最好了，伪代码也可以。（我现在只会看Python :P）

举个例子

list = [1,2,3,10]
sum = 12
result = [2,10]

注意：我知道有一个算法可以找出哪些数字加起来等于另一个数字（但我看不懂C#，也无法确认这个算法是否适合我的需求。我在用Linux，尝试过用Mono但总是出错，搞不懂C# :(
而且我也知道有一个算法可以列出所有数字组合的和（但这个效率似乎不高。我并不需要所有组合。）

Answer 1

这个逻辑是先把数字按从大到小排序，假设数字的列表叫l，要形成的总和叫s。

   for i in b:
            if(a(round(n-i,2),b[b.index(i)+1:])):
                r.append(i)    
                return True
        return False

然后，我们会通过一个循环，从l中依次选取一个数字，假设这个数字是i。这里有两种可能的情况：要么i是总和的一部分，要么不是。

我们先假设i是总和的一部分，这样问题就变成了：新的l变成了l[l.index(i+1):]，而新的s变成s-i。所以，如果我们的函数是a(l,s)，那么我们就调用a(l[l.index(i+1):], s-i)。如果i不是总和的一部分，那么我们就需要从l[l.index(i+1):]这个列表中形成s。

这两种情况其实是类似的，唯一的区别是如果i是总和的一部分，那么s就变成s-i，否则s保持不变。

现在，为了简化问题，如果l中的数字大于s，我们就把这些数字去掉，直到l为空。在这种情况下，选中的数字就不是我们要的答案，我们就返回假（false）。

if(len(b)==0):
    return False    
while(b[0]>n):
    b.remove(b[0])
    if(len(b)==0):
        return False    

如果l中只剩下一个数字，那么这个数字要么是总和的一部分，我们就返回真（true），要么不是，这样就返回假（false），然后循环会继续检查其他数字。

if(b[0]==n):
    r.append(b[0])
    return True
if(len(b)==1):
    return False

注意在循环中我用到了b，但b其实就是我们的列表。而且我在可能的地方进行了四舍五入，以避免因为浮点数计算而导致的错误答案。

r=[]
list_of_numbers=[61.12,13.11,100.12,12.32,200,60.00,145.34,14.22,100.21,14.77,214.35,200.32,65.43,0.49,132.13,143.21,156.34,11.32,12.34,15.67,17.89,21.23,14.21,12,122,134]
list_of_numbers=sorted(list_of_numbers)
list_of_numbers.reverse()
sum_to_be_formed=401.54
def a(n,b):
    global r
    if(len(b)==0):
        return False    
    while(b[0]>n):
        b.remove(b[0])
        if(len(b)==0):
            return False    
    if(b[0]==n):
        r.append(b[0])
        return True
    if(len(b)==1):
        return False
    for i in b:
        if(a(round(n-i,2),b[b.index(i)+1:])):
            r.append(i)    
            return True
    return False
if(a(sum_to_be_formed,list_of_numbers)):
    print(r)

这个解决方案运行得很快，比之前解释的那个要快多了。不过这个方法只适用于正数。如果存在解决方案，它的表现也很好，但如果没有解决方案，就会花费太多时间在循环中。

举个例子，假设

    l=[1,6,7,8,10]

and s=22 i.e. s=1+6+7+8
so it goes through like this 

1.) [10, 8, 7, 6, 1] 22
i.e. 10  is selected to be part of 22..so s=22-10=12 and l=l.remove(10)
2.) [8, 7, 6, 1] 12
i.e. 8  is selected to be part of 12..so s=12-8=4 and l=l.remove(8)
3.) [7, 6, 1] 4  
now 7,6 are removed and 1!=4 so it will return false for this execution where 8 is selected.
4.)[6, 1] 5
i.e. 7  is selected to be part of 12..so s=12-7=5 and l=l.remove(7)
now 6 are removed and 1!=5 so it will return false for this execution where 7 is selected.
5.)[1] 6
i.e. 6  is selected to be part of 12..so s=12-6=6 and l=l.remove(6)
now 1!=6 so it will return false for this execution where 6 is selected.
6.)[] 11
i.e. 1 is selected to be part of 12..so s=12-1=1 and l=l.remove(1)
now l is empty so all the cases for which 10 was a part of s are false and so 10 is not a part of s and we now start with 8 and same cases follow.
7.)[7, 6, 1] 14
8.)[6, 1] 7
9.)[1] 1

为了比较，我在我的电脑上运行了这个程序，虽然我的电脑性能不太好。

l=[61.12,13.11,100.12,12.32,200,60.00,145.34,14.22,100.21,14.77,214.35,145.21,123.56,11.90,200.32,65.43,0.49,132.13,143.21,156.34,11.32,12.34,15.67,17.89,21.23,14.21,12,122,134]

并且

s=2000

我的循环运行了1018次，耗时31毫秒。

而之前的代码循环运行了3415587次，耗时大约16秒。

不过如果没有解决方案，我的代码运行了几分钟我才停下来，而之前的代码只用了大约17毫秒，并且之前的代码也能处理负数。

所以我觉得可以做一些改进。

Answer 2

我知道你问这个问题已经过去10年了，但我真的很想知道怎么做，而jbernadas的方法对我来说太复杂了，所以我花了一个小时在网上搜索，发现了一个Python库叫做itertools，它可以解决这个问题！

希望这对未来的新手程序员有帮助。

你只需要导入这个库，然后使用.combinations()这个方法，就这么简单。它会返回一个集合中所有的子集，并且是有顺序的。我的意思是：

对于集合[1, 2, 3, 4]，如果你想要长度为3的子集，它不会返回[1, 2, 3][1, 3, 2][2, 3, 1]这些，而只会返回[1, 2, 3]。

因为你想要一个集合的所有子集，你可以这样遍历它：

import itertools

sequence = [1, 2, 3, 4]
for i in range(len(sequence)):
    for j in itertools.combinations(sequence, i):
        print(j)

输出结果将是：

() (1,) (2,) (3,) (4,) (1, 2) (1, 3) (1, 4) (2, 3) (2, 4) (3, 4) (1, 2, 3) (1, 2, 4) (1, 3, 4) (2, 3, 4)

希望这对你有帮助！

Answer 3

这个问题可以简化为一个叫做0-1背包问题，就是你需要找到一组数，它们的和正好等于一个特定的值。解决这个问题的难易程度取决于具体的限制条件，通常情况下，这个问题是NP完全的。

不过，如果你要找的和（我们称它为S）不是特别大，那么可以用动态规划来解决。我会用递归函数和记忆化来解释，这样比从底向上的方法更容易理解。

我们来写一个函数f(v, i, S)，这个函数会返回在v[i:]这个列表中，和正好等于S的子集数量。要用递归来解决，首先我们要分析基本情况（也就是：v[i:]是空的）：

• 如果S == 0：空列表[]的唯一子集和是0，所以这是一个有效的子集。因此，函数应该返回1。

• 如果S != 0：空列表[]的唯一子集和是0，所以没有有效的子集。因此，函数应该返回0。

接下来，我们分析递归情况（也就是：v[i:]不是空的）。这里有两个选择：要么把当前的数字v[i]包含在子集中，要么不包含。如果我们选择包含v[i]，那么我们就要找和为S - v[i]的子集；如果不包含，那么我们还是在找和为S的子集。函数f可以这样实现：

def f(v, i, S):
  if i >= len(v): return 1 if S == 0 else 0
  count = f(v, i + 1, S)
  count += f(v, i + 1, S - v[i])
  return count

v = [1, 2, 3, 10]
sum = 12
print(f(v, 0, sum))

通过检查f(v, 0, S) > 0，你可以知道你的问题是否有解。不过，这段代码运行得太慢了，因为每次递归调用都会产生两个新的调用，这样会导致时间复杂度是O(2^n)。现在，我们可以使用记忆化来让它的运行时间变为O(n*S)，如果S不是太大，这样会更快：

def f(v, i, S, memo):
  if i >= len(v): return 1 if S == 0 else 0
  if (i, S) not in memo:  # <-- Check if value has not been calculated.
    count = f(v, i + 1, S, memo)
    count += f(v, i + 1, S - v[i], memo)
    memo[(i, S)] = count  # <-- Memoize calculated result.
  return memo[(i, S)]     # <-- Return memoized value.

v = [1, 2, 3, 10]
sum = 12
memo = dict()
print(f(v, 0, sum, memo))

现在，我们可以编写一个函数g，它返回一个和为S的子集。要做到这一点，只需要在确保至少有一个解包含这些元素的情况下才添加它们：

def f(v, i, S, memo):
  # ... same as before ...

def g(v, S, memo):
  subset = []
  for i, x in enumerate(v):
    # Check if there is still a solution if we include v[i]
    if f(v, i + 1, S - x, memo) > 0:
      subset.append(x)
      S -= x
  return subset

v = [1, 2, 3, 10]
sum = 12
memo = dict()
if f(v, 0, sum, memo) == 0: print("There are no valid subsets.")
else: print(g(v, sum, memo))

注意：这个解决方案认为在[10, 10]中有两个子集和为10。这是因为它假设第一个10和第二个10是不同的。算法可以修改为假设两个10是相等的（因此只返回一个），但这样会复杂一些。