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