子集和问题是一个著名的 NP 完全问题。在这里,我假设您正在寻找任何一组数字来求和到目标(如果您实际上只寻找两个数字,那么有一个使用计数哈希表的五行解决方案,它在 O(n ) 时间)。
有两种基本方法。第一个只是测试每个可能的子序列。正如您已经观察到的那样,这需要 O(2 n ) 时间(指数),如果 n 为 1000,这是难以处理的。
第二个是跟踪可以从列表的前缀中获得的总和。这是一种非常简单的方法,如果整数有界,效果很好。举例来说,如果输入是 n k 位整数,它的计算复杂度为 O(2 k n 2 )(伪多项式):最大的和是 2 k n,所以表最多有 2 k n 2个条目。这是一种典型的动态规划方法,其中子问题为T[s][k] = (A[1..k] has a subsequence summing to s)
,最终解为T[target][n]
。
这是实现此功能的 Python 解决方案:
def subset_sum(A, target):
T = {0} # T[s][0] = (TRUE iff s == 0)
for i in A:
T |= {x + i for x in T}
return target in T
例子:
>>> subset_sum([-5,6,7,1,0,12,5,-6,100], 13)
True
>>> subset_sum([95, -120, 22, 14491], 13)
False
奖励:如果您好奇,这里有一个解决对和问题的方法。它在 O(n) 时间内运行,并告诉您数组是否有两个数字求和到目标。
from collections import Counter
def pair_sum(A, t):
C = Counter(A)
for k,v in C.iteritems():
if t == k+k and v > 1: return True # k is in the array twice
elif t != k+k and t-k in C: return True
return False
例子:
>>> pair_sum([3,3,3,4], 13)
False
>>> pair_sum([3,3,3,10], 13)
True
>>> pair_sum([7,7,2], 14)
True
>>> pair_sum([7,14,2], 14)
False