记S(A)为集合A中所有元素的和。若从$A$中任意两个非空i且不相交的子集B和C都满足

1. $S(B)\neq S(C)$。

2. 只要$|B|>|C|$，就有$S(B)>S(C)$。

则称A是一个特殊和集。

例如，$\{81, 88, 75, 42, 87, 84, 86, 65\}$不是特殊和集，因为$65 + 87 + 88 = 75 + 81 + 84$，而$A=\{157, 150, 164, 119, 79, 159, 161, 139, 158\}$是特殊和集，此时$S(A) = 1286$。

在文件sets.txt中有一百组包含七至十二个元素的集合（文档中的前两个集合就是上例），找出其中所有的特殊和集$A_1, A_2, \ldots, A_k$，并求$S(A_1) + S(A_2) + \ldots + S(A_k)$。

注：本题与第103题和第106题相关。

本题难度:

解答

对文件中的每个集合，先验证条件1，只需生成所有的子集并记录子集和即可。

对条件2，设集合中的元素是$a_1\le\ldots\le a_n$，则只需检验$a_1+\ldots+a_k>a_{n}+a_{n-1}+\ldots+a_{n-k+1}$对所有在2到$(n+1)/2$之间的k都成立。

结果是$73702$。

import itertools

d=[]
with open("105_sets.txt") as f:
    for line in f:
        d.append(sorted([int(i) for i in line.split(",")]))

def dss(s):
    v=set([])
    for i in range(1,len(s)+1):
        for t in itertools.combinations(s,i):
            x=sum(t)
            if x in v:
                return False
            else:
                v.add(x)
    return True
            
print sum(sum(s) for s in d if all(sum(s[:k])>sum(s[1-k:]) for k in range(2,(len(s)+1)/2+1)) and dss(s))