How to divide a list of negative and positive numbers into the largest number of subsets whose sum is 0?

Question

I am trying to solve this problem but I can't manage to figure out how.

Let's suppose I have a list of positive and negative numbers whose sum is guaranteed to be 0.

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

I want to obtain a list with the largest number of sub-sets, using all the elements of the initial list only once. And each subset must have the sum 0.

So in the case of this simple input:

[-5, -4, 5, 2, 3, -1]

The best results that can be obtained are:

1. [[-5, 5], [[-4, -1, 2, 3]]]   #2 subsets
2. [[-5, 2, 3], [-4, -1, 5]]     #2 subsets

These, for example, would be totally wrong answers:

1. [[-5, -4, -1, 2, 3, 5]]       #1 subsets that is the initial list, NO
2. [[-5,5]]                      #1 subset, and not all elements are used, NO

Even if it's NP-Complete, how can I manage to solve it even with a brute-force approach? I just need a solution for small list of numbers.

Answer 1

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]))

Basically, this solution collects all subsets of the original list that can sum to zero, then attempts to merge as many of them together as possible without colliding. It runs in worst-case O(2^{2N}) time, where N is the length of the list, but it should hit an average case of around O(2^N), since there typically shouldn't be too many subsets summing to 0.

EDIT: I added sections to facilitate explanation of the algorithm

Section 1: I iterate through all possible 2^N-1 nonempty subsets of the original list, and check which of these subsets sum to 0; any viable zero-sum subsets are added to the list cand (represented as an integer in the range [1,2^N-1] with bits set at the indices making up the subset).

Section 2: dp is a dynamic programming table storing the maximum number of subsets summing to 0 that can be formed using the subset represented by the integer i at dp[i]. Initially, all entries of dp are set to 0 except dp[0] = 1, since the empty set has a sum of 0. Then I iterate through each subset from 0 to 2^N-1, and I run through the list of candidate subsets and attempt to merge the two subsets.

Section 3: This is just backtracking to find the answer: while filling in dp, I also kept an array back that stores the most recent subset added to achieve the subset i at back[i]. So I find the subset that maximizes the number of sub-subsets summing to 0 with ind = dp.index(max(dp)), and then I backtrack from there, shrinking the subset by removing the most recently added subset until I finally arrive back to the empty set.