Задача 3-РАЗДЕЛЕНИЯ

вот еще один вопрос динамического программирования ( Vazirani ch6 )

Рассмотрим следующий 3-РАЗДЕЛ проблема. Для целых чисел a1 ... an мы хочу определить, действительно ли это возможно разбить {1 ... n} на три непересекающихся подмножества I, J, K такие что

сумма (I) = сумма (J) = сумма (K) = 1/3 * сумма (ВСЕ)

Например, для ввода (1; 2; 3; 4; 4; 5; 8) да, потому что там - разбиение (1; 8), (4; 5), (2; 3; 4). С другой стороны, для ввода (2; 2; 3; 5) ответ отрицательный. Придумать и проанализировать динамическое программирование алгоритм для 3-PARTITION, который работает в полиномиальное время в n и (Sum a_i)

Как я могу решить эту проблему? Я знаю 2 раздела, но все еще не могу его решить