Разделительный набор целых чисел

Question

У меня проблема с решением алгоритмической проблемы, как описано ниже.

У нас есть набор (например, массив) целых чисел. Наша задача - разделить их на группы (они не должны иметь такое же количество элементов), что сумма равна друг другу. В случае, когда первичный набор не может быть разделен, мы должны дать ответ «невозможно разделить».

Например: A[-7 3 3 1 2 5 14]. Ответ [-7 14], [3 3 1], [2 5].

Кажется, что легко сказать, когда наверняка это было бы невозможно. Когда сумма первичного множества не делится на 3: sum(A) % 3 != 0.

У вас есть идеи, как решить эту проблему?

Answer 1

Это 3-partition problem вариант partition problem. Разница заключается в том, что классическая проблема раздела разбивает множество на два набора (не три), суммы которых равны друг другу. Эта проблема NP-полная, поэтому вы почти наверняка не найдете для нее полиномиального решения времени; проблема 2-разбиения имеет псевдополиномиальное временное решение, но проблема 3-разбиения не имеет.

См. this answer для описания того, как адаптировать алгоритм с двумя разделами к алгоритму с 3 разделами. См. Также this paper для параллельного решения.