Largest subset from set of numbers (also negative) having sum equal 0

Question

I have a huge set of numbers with a defined order. The logic in simple terms would look like this:

data['values'] = [1,1,3,4,4,-9,10]

data['order'] = [1,2,3,4,5,6,7]

ExpectedSum = 0

What I wish to return is the original order and values of biggest possible subset of values that we can get with total sum equal 0. For this case one optimal solution would be

solution['values'] = [1,1,3,4,-9]

solution['order'] = [1,2,3,4,6]

The sum could be also achieved by replacing 4th order number with 5th order number, however, one optimal solution is enough. The goal is to reach maximum possible size of subset with total sum =0.

Was looking for variations of Knapsack problem and maximum subarray algorithms but none met my needs.

Any hints or directions appreciated.

Answer 1

All subsets of fixed length can be found with the "n choose k"-way. To find the longest the iteration starts with k=n and decreases by one.

import itertools as it

def combination_finder(l: list) -> tuple:
    for i in range(len(l)):
        for pairs in it.combinations(enumerate(l, start=0), len(l)-i):
            i, c = zip(*pairs)
            if sum(c) == 0:
                return i, c
    
    raise Exception('No combination found.')

l = [1,1,3,4,4,-9,10]
id_, comb = combination_finder(l)
print(id_)
print(comb)

Remark: to make the id_ starting from 1, simply change the enumerate as follow enumerate(l, start=1)