Subsets having same sum-python

Question

here i have an array of numbers, how to determine whether array can be divided into two subsets for which the sum of elements in both subsets is the same, if the subsets are available, the program should return true.

For array = [8, 6, 3, 5], the output should be sub(array) = true

It is possible to partition this array into two subsets that have a sum of 8: [8] and [3,5].

`

Answer 1

Here's a brute-force solution. It uses the powerset recipe from the Itertools Recipes in the docs to generate all the subsets. It then sorts and groups them by sum, using itertools.groupby. Then finally it checks all pairs of subsets with the same sum to find pairs that do not intersect.

from itertools import chain, combinations, groupby

def equal_sum_partitions(seq):
    subsets = chain.from_iterable(combinations(seq, r) for r in range(len(seq)+1))
    for k, g in groupby(sorted(subsets, key=sum), key=sum):
        group = [set(u) for u in g]
        if len(group) > 1:
            for u, v in combinations(group, 2):
                if not u & v:
                    print(k, (u, v))

# test

equal_sum_partitions([2, 4, 8, 6, 3, 5])  

output

5 ({5}, {2, 3})
6 ({6}, {2, 4})
7 ({2, 5}, {3, 4})
8 ({8}, {2, 6})
8 ({8}, {3, 5})
8 ({2, 6}, {3, 5})
9 ({4, 5}, {3, 6})
10 ({8, 2}, {4, 6})
10 ({4, 6}, {2, 3, 5})
11 ({8, 3}, {5, 6})
11 ({8, 3}, {2, 4, 5})
13 ({8, 5}, {3, 4, 6})
14 ({8, 6}, {2, 3, 4, 5})
14 ({8, 2, 4}, {3, 5, 6})