具有相同总和的子集-python [英] Subsets having same sum-python

问题描述

这里我有一个数字数组，如何确定数组是否可以分为两个子集，两个子集中的元素之和是相同的，如果这些子集可用，则程序应返回true.

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

可以将此数组划分为两个子集，每个子​​集的总和为8:[8]和[3,5].

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

`

推荐答案

这是一种蛮力解决方案.它使用 Itertools食谱中的powerset食谱在文档中生成所有子集.然后，它使用 itertools.groupby对它们进行汇总和分组. .最后，它检查所有具有相同总和的子集对，以找到不相交的对.

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

输出

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

这篇关于具有相同总和的子集-python的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！