计算数组的所有子集,其中最大数字是剩余数字的总和

Question

我一直在努力应对Greplin挑战赛的第3级.对于那些不熟悉的人,问题是:

您必须找到数组的所有子集,其中最大数字是剩余数字的总和.例如,输入:

(1,2,3,4,6)

子集将是

1 + 2 = 3

1 + 3 = 4

2 + 4 = 6

1 + 2 + 3 = 6

以下是您应该运行代码的数字列表.密码是子集的数量.在上面的例子中,答案是4.

3,4,9,14,15,19,28,37,47,50,54,56,59,61,70,73,78,81,92,95,97,99

我能够编写一个解决方案来构建22个数字的所有400万个组合,然后对它们进行全部测试,这将得到正确的答案.问题是需要40多分钟才能完成.在网络上搜索似乎有几个人能够在不到一秒的时间内编写算法来获得答案.任何人都可以用伪代码解释比计算上昂贵的暴力方法更好的解决方法吗？这让我疯了!

Answer 1

诀窍在于,您只需要跟踪有多少种方法可以做的事情.由于数字是排序和正数,这很容易.这是一个有效的解决方案.(我的笔记本电脑需要不到0.03秒.)

#! /usr/bin/python

numbers = [
    3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56,
    59, 61, 70, 73, 78, 81, 92, 95, 97, 99]

max_number = max(numbers)
counts = {0: 1}
answer = 0
for number in numbers:
    if number in counts:
        answer += counts[number]
    prev = [(s,c) for (s, c) in counts.iteritems()]
    for (s, c) in prev:
        val = s+number;
        if max_number < val:
            continue
        if val not in counts:
            counts[val] = c
        else:
            counts[val] += c
print answer

Answer 2

我使用了 Java 中的组合生成器类：

http://www.merriampark.com/comb.htm

迭代组合并寻找有效的子集花费了不到一秒的时间。（我认为使用外部代码不符合挑战，但我也没有申请。）