Учитывая массив целых чисел, создайте разделы, в которых сумма элементов в каждом разделе равна 0, а максимальное количество разделов не сформировано.

Это определенно имеет NP-жесткий вид. В частности, вопрос о том, можно ли сделать 2 раздела вместо 1, - это вопрос о том, составляет ли правильное подмножество всех элементов, кроме последнего, отрицательное значение последнего, что является вариантом проблемы суммы подмножества. Таким образом, даже проверка того, что ответ нельзя улучшить путем разделения одного из разделов, вероятно, является NP-полной!

Но как решить это на практике?

Шаг 1 — создать структуру данных, представляющую все возможные разделы, включая первый элемент, сумма которых равна 0. Это можно решить, как в стандартном алгоритме суммирования подмножеств. С идеей двусвязного списка, из которого мы можем получить информацию. (Двусвязный список, как правило, будет пропорционален размеру вашего массива, умноженному на количество найденных различных сумм, но при декодировании он может привести к экспоненциальному количеству разделов.

Двусвязные списки могут вызвать у вас головокружение, поэтому вы, вероятно, захотите использовать синтаксический сахар следующим образом:

from collections import namedtuple
Node = namedtuple('Node', ['ind', 'prev'])
Paths = namedtuple('Paths', ['node', 'prev'])

Где ind — это индекс вашего массива, node — всегда Node, а prev — всегда Paths или None.

И теперь Node говорит: «включите этот индекс и любой допустимый путь в следующие предыдущие варианты». И Paths говорит "вот узел, который ведет сюда, и предыдущие пути для других путей".

При этом мы можем сделать следующее:

# We only want paths that take the 0th index.
ways_to_get_to_n = {elements[0], Paths(Node(0, None), None)}

for i in range(1, len(elements)):
    element = elements[i]
    new_ways_to_get_n = {}
    for value, ways in ways_to_get_n.items():
        new_ways_to_get_n[value] = ways
    for value, ways in ways_to_get_n.items():
        if value + element not in new_ways_to_get_n:
            new_ways_to_get_n[value + element] = Paths(Node(i, ways), None)
        else:
            new_ways_to_get_n[value + element] = Paths(Node(i, ways), new_ways_to_get_n[value + element])
    ways_to_get_n = new_ways_to_get_n

Когда вы закончите, ways_to_get_n[0] будет довольно краткой структурой данных, которую можно использовать с двойной рекурсией для обхода всех разделов, содержащих первый элемент. Однако есть проблема. Внутри этих разделов может быть 0 разделов. Поэтому, когда вы проходите двойную рекурсию, носите с собой структуру данных всех значений, которых вы можете достичь (тот же старый трюк с суммой подмножеств), и завершайте работу раньше, когда появляется 0. (Эта бухгалтерия может показаться большой дополнительной работой, но на самом деле она сэкономит вам гораздо больше.)

И теперь вы можете рекурсивно находить минимальные разделы с первым элементом. Затем рекурсивно ищите, как разделить оставшиеся элементы. Каждый раз, когда вы это делаете, вы сравниваете с лучшим, что у вас есть на данный момент, и если это улучшение, записывайте это.

Когда вы использовали все способы его разложения, все готово.

Предполагая массивы целых чисел (поэтому псевдополиномиальная сумма подмножества, вероятно, будет работать в вашу пользу), это позволит вам довольно эффективно выполнять рекурсию на минимальных разделах. Что лучше рекурсивного взрыва, чем наивный подход. Но он будет намного больше, чем вы думаете.

Я подозреваю, что сортировка массива по возрастанию абсолютного значения в качестве первого шага сделает этот алгоритм более эффективным, поскольку «фильтр для неприводимого раздела» может выйти из рекурсии раньше, когда у вас еще много элементов.

Я согласен, что проблема в НП. Оптимизировать это некрасиво, с большой буквы "тьфу". Вы можете несколько улучшить время поиска, но я боюсь, что оно по-прежнему O(2^N) и хуже.

• Разделите список на положительные и отрицательные числа; отсортировать оба списка.
• Для каждого элемента более короткого списка найдите его дополнение в другом. Каждая такая пара является разделом; их можно смело заносить в список решений и удалять из дальнейшей обработки.

Теперь идут уродливые части. «Относительный» подход грубой силы состоит в том, чтобы сгенерировать набор мощности каждого раздела; индекс по сумме. Например, для списка 2, 3, 4, 7:

 2  [2]
 3  [3]
 4  [4]
 5  [2, 3]
 6  [2, 4]
 7  [7] [3, 4]
 9  [2, 7] [2, 3, 4]
10  [3, 7]
11  [4, 7]
12  [2, 3, 7]
13  [2, 4, 7]
14  [3, 4, 7]
16  [2, 3, 4, 7]

Теперь найдите все совпадения abs(sum(subset)) между положительными и отрицательными списками. Они формируют выбор для вашего пространства решений. Моя лучшая рекомендация с этого момента — применить set coverage problem к этому; вам придется немного настроить повторяющиеся значения.