CODEWITHSUNDEEP
pythonlist
LegoCamel
LegoCamel

Reputation: 45

Given a list of integers how do I check if it is possible to get 2 sublists of equal sum?

Given a single parameter (list of integers), return True if it's possible to get 2 sublists of equal sum, return False if it's not.

What I had initially was to initialize the 2 sublists first and start appending the integers from the sorted list into the sublist which has the smaller total sum.

def split_ls(arr):
    arr.sort()
    a = []
    b = []
    while arr:
        push = arr.pop()
        if sum(a) == sum(b) or push == 0:
            a.append(push)
        elif sum(a) > sum(b):
            if push < 0:
                a.append(push)
            else:
                b.append(push)
        else:
            if push < 0:
                b.append(push)
            else:
                a.append(push)

    if sum(a) == sum(b):
        return True
    else:
        return False

This would work for some test cases but not for all like... arr = [7, -3, 6, 1, 10, -4, 2, 2, 6, 7, -3, 2, 4, 0, 7, 6, -2, 10, -4, 10]

Upvotes: 1

Views: 401

Answers (1)

Thierry Lathuille
Thierry Lathuille

Reputation: 24242

This is a case of the partition problem, which is NP-hard.

A rather 'brute' way to to it is to try all possible combinations of 1, 2... up to half the number of values in the list to find one that adds to half the total sum.

It might be good to estimate the number of such combinations before trying to run the code. We need to test at most half the number of subsets of your list of length n, so 2^n / 2 = 2^(n-1).

For your list of 20 values, that would be 2^19 = 524288, which can still be done in reasonable time.

So, we can try combinations generated using itertools.combinations until we find one with half the sum, then build the other half list by removing the values we found from the original list:

from itertools import combinations 


def find_half_sum(arr):
    half_sum = sum(arr)/2

    for comb_size in range(1, len(arr)//2 + 1):
        for comb in combinations(arr, comb_size):
            if sum(comb) == half_sum:
                second = arr[:]
                for v in first:
                    second.remove(v)
                return(first, second)
            
    raise ValueError("Can't split this array in equal sums")
    
arr = [7, -3, 6, 1, 10, -4, 2, 2, 6, 7, -3, 2, 4, 0, 7, 6, -2, 10, -4, 10]
first, second = find_half_sum(arr)
    
print(first, sum(first))
print(second, sum(second))

#(6, 10, 6, 10) 32
#[7, -3, 1, -4, 2, 2, 7, -3, 2, 4, 0, 7, 6, -2, -4, 10] 32

Upvotes: 1

Related Questions