Subsets Having Same Sum-python

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 availa

Solution 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

defequal_sum_partitions(seq):
    subsets = chain.from_iterable(combinations(seq, r) for r inrange(len(seq)+1))
    for k, g in groupby(sorted(subsets, key=sum), key=sum):
        group = [set(u) for u in g]
        iflen(group) > 1:
            for u, v in combinations(group, 2):
                ifnot 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})

Solution 2:

I found a solution, but it will raise a memory error for larger inputs :(

def subs(l):
 if l == []:
    return[[]]
x = subs(l[1:])
return x + [[l[0]] + y for y in x]

def sub(arr):
ls=[]
ls=subs(arr)
for i in ls:
    if(sum(list(set(arr)-set(i)))==sum(i)):
        return True
return False