Count all subsets of an array where the largest number is the sum of the remaining numbers

Question

I've been struggling with level 3 of the Greplin challenge. For those not familiar, here is the problem:

you must find all subsets of an array where the largest number is the sum of the remaining numbers. For example, for an input of:

(1, 2, 3, 4, 6)

the subsets would be

1 + 2 = 3

1 + 3 = 4

2 + 4 = 6

1 + 2 + 3 = 6

Here is the list of numbers you should run your code on. The password is the number of subsets. In the above case the answer would be 4.

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

I was able to code a solution that builds all 4 million plus combinations of the 22 numbers and then tests them all which will get me the right answer. Problem is it takes over 40 minutes to crunch through. Searching around the web it seems like several people were able to write an algorithm to get the answer to this in less than a second. Can anyone explain in pseudo-code a better way to tackle this than the computationally expensive brute-force method? It's driving me nuts!

Answer 1

The trick is that you only need to keep track of counts of how many ways there are to do things. Since the numbers are sorted and positive, this is pretty easy. Here is an efficient solution. (It takes under 0.03s on my laptop.)

#! /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