105. 特殊的子集和:检验(Special subset sums: testing)
设\(S(A)\)是大小为\(n\)的集合\(A\)中所有元素的和,若任取集合\(A\)中的任意两个非空且没有交集的子集\(B\)和\(C\)都满足下面两个条件,我们就称\(A\)是的特殊的和集:
- \(S(B)\ne S(C)\),也就是说任意子集所有元素的和均不相同;
- 如果集合\(B\)中的元素比集合\(C\)多,则\(S(B)>S(C)\)。
例如\(\{81, 88, 75, 42, 87, 84, 86, 65\}\)不是一个特殊和集,因为\(65 + 87 + 88 = 75 + 81 + 84\),而集合\(\{157, 150, 164, 119, 79, 159, 161, 139, 158\}\)满足上述规则且相应的\(S(A) = 1286\)。
在4k的文本文件sets.txt中包含了一百组包含七至十二个元素的集合(文档中的前两个例子就是上述样例),找出所有的特殊和集\(A_1, A_2, \ldots, A_k\)并求\(S(A_1) + S(A_2) + \ldots + S(A_k)\)的值。
分析:在第103题中我们已经编写了一个判断特定集合是否是特殊和集的函数,这里只需要拿过来用就可以了,关于这个函数的具体解释可以直接参照103题的题解,这里不再做详细的解释,代码如下:
# time cost = 13.7 s ± 736 ms
from itertools import combinations
def is_valid(B,tup):
L,S = tup
if len(B) == L:
return sum(B) != S
else:
return (sum(B)-S)*(len(B)-L)>0
def is_special_sumsets(s):
arr = [(1,x) for x in sorted(s)]
for r in range(2,len(s)):
for i in combinations(sorted(s),r):
for j in arr:
if not is_valid(i,j):
return False
arr.append((len(i),sum(i)))
return True
def main():
res = 0
with open('data/pe105.txt') as f:
sets = [[int(x) for x in row.strip().split(',')] for row in f.readlines()]
for s in sets:
if is_special_sumsets(s):
res += sum(s)
return res