Searching for subsets (interesting complex task)

Question

I've just been doing Greplin programming challenge and went to the final level, where the task sounds like this:

For the final task, 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 (3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61, 70, 73, 78, 81, 92, 95, 97, 99) 
you should run your code on.
The password is the number of subsets.  In the above case the
answer would be 4.

Can you give me a suggestion what should I do here? I think brute-force doesn't fit here, does it?

Don't write code!

Thank you.

Answer 1

Use dynamic programming, solutions for smaller numbers can be extended to solutions for bigger numbers.

Answer 2

I brute forced this problem (in Python) and got an answer in less than a minute. What helped (and here was a hint) was support in the Python library itertools for generating N-length combinations of an array/list/sequence.

To generate all possible subsets of an array, first generate the possible 1-length subsets, then 2-length subsets, then 3-length subsets, up to N-length. Without a good library to provide a combinations() function for you to use, one possible approach when coding this yourself would be to use recursion.