java - 搜索子集(有趣的复杂任务)

Question

我刚刚在做Greplin programming challenge然后进入最后一关，任务听起来是这样的:

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.

你能给我一个建议我应该在这里做什么吗？我认为蛮力不适合这里，是吗？

不要写代码!

谢谢。

Answer 1

使用dynamic programming ，较小数字的解决方案可以扩展到较大数字的解决方案。