Подмножества, имеющие одинаковый сумма-питон

Question

здесь у меня есть массив чисел, как определить, можно ли разделить массив на два подмножества, для которых сумма элементов в обоих подмножествах одинакова, если подмножества доступны, программа должна return true.

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

Можно разделить этот массив на два подмножества, которые имеют сумму 8: [8] и [3,5].

`

Answer 1

Вот перебором решение. Он использует рецепт poweret от Itertools Recipes в документах для создания всех подмножеств. Затем он сортирует и группирует их по сумме, используя itertools.groupby. Затем, наконец, он проверяет все пары подмножеств с одинаковой суммой, чтобы найти пары, которые не пересекаются.

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

выход

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

Answer 2

Я нашел решение, но он поднимет ошибку памяти для больших входов :(

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