def get_subsets(lst):
    N = len(lst)
    cand = []
    dp = [0 for x in range(1<<N)]   # maximum number of subsets using elements represented by bitset
    back = [0 for x in range(1<<N)]

    # Section 1
    for i in range(1,1<<N):
        cur = 0
        for j in range(N):
            if i&(1<<j):
                cur += lst[j]
        if not cur:
            cand.append(i)     # if subset sums to 0, it's viable
    dp[0] = 1

    # Section 2
    for i in range(1<<N):
        while cand and cand[0] <= i:
            cand.pop(0)
        if not dp[i]:
            continue
        for j in cand:
            if i&j:     # if subsets intersect, it cannot be added
                continue
            if dp[i]+1 > dp[i|j]:
                back[i|j] = j
                dp[i|j] = dp[i]+1

    # Section 3
    ind = dp.index(max(dp))
    res = []

    while back[ind]:
        cur = []
        for i in range(N):
            if back[ind]&(1<<i):
                cur.append(lst[i])
        res.append(cur)
        ind = ind^back[ind]

    return res

print (get_subsets([-5, -4, 5, 2, 3, -1]))

По сути, это решение собирает все подмножества исходного списка, сумма которых может равняться нулю, а затем пытается объединить как можно больше из них без столкновений. Он выполняется в худшем случае за время O(2^{2N}), где N — длина списка, но в среднем он должен достигать O(2^N), поскольку обычно их не должно быть слишком много. подмножества в сумме равны 0.

РЕДАКТИРОВАТЬ: я добавил разделы, чтобы облегчить объяснение алгоритма

Раздел 1: я перебираю все возможные 2^N-1 непустых подмножеств исходного списка и проверяю, сумма каких из этих подмножеств равна 0; любые жизнеспособные подмножества с нулевой суммой добавляются в список cand (представленный как целое число в диапазоне [1,2^N-1] с битами, установленными в индексах, составляющих подмножество).

Раздел 2: dp — это таблица динамического программирования, в которой хранится максимальное количество подмножеств, суммирующихся с 0, которые могут быть сформированы с использованием подмножества, представленного целым числом i в dp[i]. Первоначально все элементы dp устанавливаются равными 0, кроме dp[0] = 1, поскольку сумма пустого набора равна 0. Затем я перебираю каждое подмножество от 0 до 2^N-1, просматриваю список подмножеств-кандидатов и пытаюсь объединить два подмножества.

Раздел 3: Это просто возврат, чтобы найти ответ: при заполнении dp я также сохранил массив back, в котором хранится самое последнее добавленное подмножество для получения подмножества i в back[i]. Итак, я нахожу подмножество, которое максимизирует количество подмножеств, суммирующихся с 0 с помощью ind = dp.index(max(dp)), а затем возвращаюсь оттуда, уменьшая подмножество, удаляя последнее добавленное подмножество, пока, наконец, не вернусь к пустому набору.

Эта задача является NP-полной, так как представляет собой комбинацию двух NP-полных задач:

• поиск единственного подмножества, сумма которого равна 0, известен как проблема суммы подмножества
• когда вы найдете все подмножества, сумма которых равна 0, вам нужно решить задачу точного покрытия с особое условие: вы хотите максимизировать количество подмножеств.

Следующие шаги обеспечат решение:

• используйте динамическое программирование, чтобы найти подмножества, сумма которых равна 0 ('https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution)
• чтобы максимизировать количество подмножеств, можно использовать D. Алгоритм Кнута X для нахождения точного покрытия.

Несколько замечаний:

1. Во-первых, мы знаем, что существует точное покрытие, потому что сумма списка чисел равна 0.

2. Во-вторых, мы можем использовать только те подмножества, которые не являются надмножествами какого-либо другого подмножества. Потому что, если A является надмножеством X (оба в сумме дают 0), A не может быть в покрытии с наибольшим количеством подмножеств. Пусть A, B, C, ... - покрытие с максимальным числом подмножеств, тогда мы можем заменить A на X и A\X (тривиально видно, что сумма A\X элементов равна 0) и мы получим покрытие X , A\X, B, C, ... то лучше.

3. В-третьих, когда мы используем алгоритм X, все пути в дереве поиска приведут к успеху. Пусть A, B, C, ... будет путем, состоящим из непересекающихся подмножеств, каждое из которых имеет сумму 0. Тогда у комплента также есть сумма 0 (которая может быть надмножеством другого подмножества, и тогда мы будем использовать 2.).

Как видите, здесь нет ничего нового, и я буду использовать только известные методы/алгоритмы.

Найдите подмножества, сумма которых равна 0.

Алгоритм известен. Вот реализация Python, основанная на объяснениях из Википедии

class Q:
    def __init__(self, values):
        self.len = len(values)
        self.min = sum(e for e in values if e <= 0)
        self.max = sum(e for e in values if e >= 0)
        self._arr = [False] * self.len * (self.max - self.min + 1)

    def __getitem__(self, item):
        index, v = item
        return self._arr[v * self.len + index]

    def __setitem__(self, item, value):
        index, v = item
        self._arr[v * self.len + index] = value


class SubsetSum:
    def __init__(self, values):
        self._values = values
        self._q = Q(values)

    def prepare(self):
        for s in range(self._q.min, self._q.max + 1):
            self._q[0, s] = (self._values[0] == s)
        for i in range(self._q.len):
            self._q[i, 0] = True

        for i in range(1, self._q.len):
            v = self._values[i]
            for s in range(self._q.min, self._q.max + 1):
                self._q[i, s] = (v == s) or self._q[i - 1, s] or self._q[
                    i - 1, s - v]

    def subsets(self, target=0):
        yield from self._subsets(self._q.len - 1, target, [])

    def _subsets(self, i, target, p):
        assert i >= 0
        v = self._values[i]
        c = self._q[i - 1, target]
        b = self._q[i - 1, target - v]
        if i == 0:
            if target == 0:
                if p:
                    yield p
            elif self._q[0, target]:
                yield p + [i]
        else:
            if self._q.min <= target - v <= self._q.max and self._q[
                i - 1, target - v]:
                yield from self._subsets(i - 1, target - v, p + [i])

            if self._q[i - 1, target]:
                yield from self._subsets(i - 1, target, p)

Вот как это работает:

arr = [-10, 1, 2, 20, 5, -100, -80, 10, 15, 15, 60, 100, -20, -18]
arr = sorted(arr)
s = SubsetSum(arr)
s.prepare()
subsets0 = list(s.subsets())
print(subsets0)

Выход:

[[13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0], [13, 12, 11, 10, 9, 7, 6, 5, 3, 2, 1, 0], [13, 12, 11, 10, 9, 4, 2, 1, 0], [13, 12, 11, 10, 8, 7, 4, 2, 1, 0], [13, 12, 11, 10, 8, 6, 5, 4, 3, 1, 0], [13, 12, 11, 10, 7, 2, 1, 0], [13, 12, 11, 10, 6, 5, 3, 1, 0], [13, 12, 11, 9, 8, 7, 4, 2, 1, 0], [13, 12, 11, 9, 8, 6, 5, 4, 3, 1, 0], [13, 12, 11, 9, 7, 2, 1, 0], [13, 12, 11, 9, 6, 5, 3, 1, 0], [13, 12, 11, 8, 7, 6, 5, 3, 1, 0], [13, 12, 11, 8, 4, 1, 0], [13, 12, 11, 1, 0], [13, 12, 10, 9, 8, 7, 6, 5, 4, 3, 1, 0], [13, 12, 10, 9, 8, 2, 1, 0], [13, 12, 10, 9, 7, 6, 5, 3, 1, 0], [13, 12, 10, 9, 4, 1, 0], [13, 12, 10, 8, 7, 4, 1, 0], [13, 12, 10, 7, 1, 0], [13, 12, 9, 8, 7, 4, 1, 0], [13, 12, 9, 7, 1, 0], [13, 11, 10, 8, 6, 5, 4, 3, 2, 0], [13, 11, 10, 6, 5, 3, 2, 0], [13, 11, 9, 8, 6, 5, 4, 3, 2, 0], [13, 11, 9, 6, 5, 3, 2, 0], [13, 11, 8, 7, 6, 5, 3, 2, 0], [13, 11, 8, 4, 2, 0], [13, 11, 7, 6, 5, 4, 3, 2, 1], [13, 11, 7, 6, 5, 4, 3, 0], [13, 11, 2, 0], [13, 10, 9, 8, 7, 6, 5, 4, 3, 2, 0], [13, 10, 9, 7, 6, 5, 3, 2, 0], [13, 10, 9, 4, 2, 0], [13, 10, 8, 7, 4, 2, 0], [13, 10, 8, 6, 5, 4, 3, 2, 1], [13, 10, 8, 6, 5, 4, 3, 0], [13, 10, 7, 2, 0], [13, 10, 6, 5, 3, 2, 1], [13, 10, 6, 5, 3, 0], [13, 9, 8, 7, 4, 2, 0], [13, 9, 8, 6, 5, 4, 3, 2, 1], [13, 9, 8, 6, 5, 4, 3, 0], [13, 9, 7, 2, 0], [13, 9, 6, 5, 3, 2, 1], [13, 9, 6, 5, 3, 0], [13, 8, 7, 6, 5, 3, 2, 1], [13, 8, 7, 6, 5, 3, 0], [13, 8, 4, 2, 1], [13, 8, 4, 0], [13, 7, 6, 5, 4, 3, 1], [13, 2, 1], [13, 0], [12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1], [12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 0], [12, 11, 10, 9, 8, 2, 0], [12, 11, 10, 9, 7, 6, 5, 3, 2, 1], [12, 11, 10, 9, 7, 6, 5, 3, 0], [12, 11, 10, 9, 4, 2, 1], [12, 11, 10, 9, 4, 0], [12, 11, 10, 8, 7, 4, 2, 1], [12, 11, 10, 8, 7, 4, 0], [12, 11, 10, 8, 6, 5, 4, 3, 1], [12, 11, 10, 7, 2, 1], [12, 11, 10, 7, 0], [12, 11, 10, 6, 5, 3, 1], [12, 11, 9, 8, 7, 4, 2, 1], [12, 11, 9, 8, 7, 4, 0], [12, 11, 9, 8, 6, 5, 4, 3, 1], [12, 11, 9, 7, 2, 1], [12, 11, 9, 7, 0], [12, 11, 9, 6, 5, 3, 1], [12, 11, 8, 7, 6, 5, 3, 1], [12, 11, 8, 4, 1], [12, 11, 1], [12, 10, 9, 8, 7, 6, 5, 4, 3, 1], [12, 10, 9, 8, 2, 1], [12, 10, 9, 8, 0], [12, 10, 9, 7, 6, 5, 3, 1], [12, 10, 9, 4, 1], [12, 10, 8, 7, 4, 1], [12, 10, 7, 1], [12, 9, 8, 7, 4, 1], [12, 9, 7, 1], [11, 10, 8, 6, 5, 4, 3, 2], [11, 10, 6, 5, 3, 2], [11, 9, 8, 6, 5, 4, 3, 2], [11, 9, 6, 5, 3, 2], [11, 8, 7, 6, 5, 3, 2], [11, 8, 4, 2], [11, 7, 6, 5, 4, 3], [11, 2], [10, 9, 8, 7, 6, 5, 4, 3, 2], [10, 9, 7, 6, 5, 3, 2], [10, 9, 4, 2], [10, 8, 7, 4, 2], [10, 8, 6, 5, 4, 3], [10, 7, 2], [10, 6, 5, 3], [9, 8, 7, 4, 2], [9, 8, 6, 5, 4, 3], [9, 7, 2], [9, 6, 5, 3], [8, 7, 6, 5, 3], [8, 4]]

Уменьшите количество подмножеств

У нас есть 105 подмножеств, сумма которых равна 0, но мы можем удалить подмножества, являющиеся надмножеством других подмножеств. Нам нужна функция, чтобы найти, содержит ли список элементов все элементы в другом списке. В Питоне:

import collections

def contains(l1, l2):
    """
    Does l1 contain all elements of l2?
    """
    c = collections.Counter(l1)
    for e in l2:
        c[e] -= 1
    return all(n >= 0 for n in c.values())

Теперь мы можем удалить подмножества, которые являются надмножествами другого подмножества.

def remove_supersets(subsets):
    subsets = sorted(subsets, key=len)
    new_subsets = []
    for i, s1 in enumerate(subsets):
        for s2 in subsets[:i]: # smaller subsets
            if contains(s1, s2):
                break
        else:  # not a superset
            new_subsets.append(s1)
    return new_subsets

В нашей ситуации:

subsets0 = remove_supersets(subsets0)
print(len(subsets0))

Выход:

[[13, 0], [11, 2], [8, 4], [13, 2, 1], [12, 11, 1], [10, 7, 2], [9, 7, 2], [12, 10, 7, 1], [12, 9, 7, 1], [10, 9, 4, 2], [10, 6, 5, 3], [9, 6, 5, 3], [12, 11, 10, 7, 0], [12, 11, 9, 7, 0], [12, 10, 9, 8, 0], [12, 10, 9, 4, 1], [8, 7, 6, 5, 3], [12, 11, 10, 9, 4, 0], [12, 10, 9, 8, 2, 1], [11, 7, 6, 5, 4, 3], [13, 7, 6, 5, 4, 3, 1]]
[[0, 2, 10, 6, 4], [0, 2, 10, 8, 1], [0, 2, 11, 5, 4], [0, 2, 11, 7, 1], [0, 16, 9, 4], [0, 16, 15, 1], [0, 18, 19], [3, 2, 12, 11], [3, 2, 13, 10], [3, 17, 16], [3, 19, 14], [20, 14, 1]]

Нам удалось сократить количество подмножеств до 21, что является хорошим улучшением, так как нам нужно изучить все возможности, чтобы найти точное покрытие.

Алгоритм Х

Я не использую здесь танцующие ссылки (я думаю, что этот метод мы разработаем для языков низкого уровня, таких как C, но вы можете реализовать их на Python, если хотите). Нам просто нужно отслеживать оставшиеся подмножества:

class Matrix:
    def __init__(self, subsets, ignore_indices=set()):
        self._subsets = subsets
        self._ignore_indices = ignore_indices

    def subset_values(self, i):
        assert i not in self._ignore_indices
        return self._subsets[i]

    def value_subsets_indices(self, j):
        return [i for i, s in self._subsets_generator() if j in s]

    def _subsets_generator(self):
        return ((i, s) for i, s in enumerate(self._subsets) if
                i not in self._ignore_indices)

    def rarest_value(self):
        c = collections.Counter(
            j for _, s in self._subsets_generator() for j in s)
        return c.most_common()[-1][0]

    def take_subset(self, i):
        s = self._subsets[i]
        to_ignore = {i2 for i2, s2 in self._subsets_generator() if
                     set(s2) & set(s)}
        return Matrix(self._subsets,
                      self._ignore_indices | to_ignore)

    def __bool__(self):
        return bool(list(self._subsets_generator()))

И, наконец, функция cover:

def cover(m, t=[]):
    if m: # m is not empty
        j = m.rarest_value()
        for i in m.value_subsets_indices(j):
            m2 = m.take_subset(i)
            yield from cover(m2, t + [i])
    else:
        yield t

Наконец, мы имеем:

m = Matrix(subsets0)
ts = list(cover(m))
t = max(ts, key=len)
print([[arr[j] for j in subsets0[i]] for i in t])

Выход:

[[100, -100], [10, -10], [15, 2, 1, -18], [15, 5, -20], [60, 20, -80]]

Ниже по сути та же идея, что и у Майкла Хуанга, но еще 30 строк...

Решение с кликами

1. Мы можем предварительно построить все подмножества, сумма которых равна 0.

   • Build subsets of 1 elem;
   • затем размера 2 путем повторного использования предыдущих
   • и держать тех, чья сумма равна нулю по пути

Теперь скажем, что такое подмножество является узлом графа. Тогда узел связан с другим тогда и только тогда, когда их ассоциированное подмножество не имеет общего числа.

2. Таким образом, мы хотим построить максимальную клику графа:

   • In a clique, all nodes are in relation idem their subsets are disjoints
   • Максимальная клика дает нам максимальное количество подмножеств

function forall (v, reduce) {
  const nexts = v.map((el, i) => ({ v: [el], i, s: el })).reverse()
  while (nexts.length) {
    const next = nexts.pop()
    for (let i = next.i + 1; i < v.length; ++i) {
      const { s, skip } = reduce(next, v[i])
      if (!skip) {
        nexts.push({ v: next.v.concat(v[i]), s: s, i })
      }
    }
  }
}
function buildSubsets (numbers) {
  const sums = []
  forall(numbers, (next, el) => {
    const s = next.s + el
    if (s === 0) {
      sums.push({ s, v: next.v.concat(el) })
      return { s, skip: true }
    }
    return { s }
  })
  return sums
}
const bin2decs = bin => {
  const v = []
  const s = bin.toString(2)
  for (let i = 0; i < s.length; ++i) {
    if (intersects(dec2bin(i), bin)) {
      v.push(i)
    }
  }
  return v
}
const dec2bin = dec => Math.pow(2, dec)
const decs2bin = decs => decs.reduce((bin, dec) => union(dec2bin(dec), bin), 0)
// Set methods on int
const isIn = (a, b) => (a & b) === a
const intersects = (a, b) => a & b
const union = (a, b) => a | b

// if a subset contains another one, discard it
// e.g [1,2,4] should be discarded if [1,2] is present
const cleanSubsets = bins => bins.filter(big => bins.every(b => big === b || !isIn(b, big)))
function bestClique (decs) {
  const cliques = []
  forall(decs, (next, el) => {
    if (intersects(next.s, el)) { return { skip: true } }
    const s = union(next.s, el)
    cliques.push({ s, v: next.v.concat(el) })
    return { s }
  })
  return cliques.sort((a, b) => b.v.length - a.v.length)[0]
}
// in case we have duplicated numbers in the list,
// they are still uniq thanks to their id: i (idem position in the list)
const buildNumbers = v => v.map((n, i) => {
  const u = new Number(n)
  u.i = i
  return u
})
function run (v) {
  const numbers = buildNumbers(v)
  const subs = buildSubsets(numbers)
  const bins = subs.map(s => decs2bin(s.v.map(n => n.i)))
  const clique = bestClique(cleanSubsets(bins))
  const indexedSubs = clique.v.map(bin2decs)
  const subsets = indexedSubs.map(sub => sub.map(i => numbers[i].valueOf()))
  console.log('subsets', JSON.stringify(subsets))
}

run([1, -1, 2, -2])
run([-10, 1, 2, 20, 5, -100, -80, 10, 15, 15, 60, 100, -20, -18, 10, -10])
run([-5, -4, 5, 2, 3, -1])