Поиск подмножеств (интересная сложная задача)

Question

Я только что выполнил Задачу по программированию Greplin и перешел на последний уровень, где задача звучит так:

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

Использование динамическое программирование , решения для меньших чисел можно распространить на решения для больших чисел.

Answer 2

Я перебрал эту проблему (в Python) и получил ответ менее чем за минуту.Помогло (и здесь был намек) поддержка в библиотеках Python itertools для создания комбинаций массива / списка / последовательности N-длины.

Для создания всех возможных подмножеств массивасначала генерируют возможные подмножества 1 длины, затем подмножества 2 длины, затем подмножества 3 длины, вплоть до N длины.Без хорошей библиотеки, предоставляющей вам функцию комбинаций () , одним из возможных подходов при ее самостоятельном кодировании было бы использование рекурсии.