Statement

Let S(A) represent the sum of elements in set A of size n. We shall call it a special sum set if for any two non-empty disjoint subsets, B and C, the following properties are true:

• S(B) S(C); that is, sums of subsets cannot be equal.
• If B contains more elements than C then S(B) S(C).

For example, {81, 88, 75, 42, 87, 84, 86, 65} is not a special sum set because 65 + 87 + 88 = 75 + 81 + 84, whereas {157, 150, 164, 119, 79, 159, 161, 139, 158} satisfies both rules for all possible subset pair combinations and S(A) = 1286.

Using sets.txt, a 4K text file with one-hundred sets containing seven to twelve elements (the two examples given above are the first two sets in the file), identify all the special sum sets, A₁, A₂, …, A_k, and find the value of S(A₁) + S(A₂) + … + S(A_k).

Solution

The key point to this solution is to find an efficient way to determine whether a certain set has or hasn't each of the properties.

Checking the second property

The easiest property to determine is the second one. To see if that property is true for that set we just need to compare the smallest subset B with the highest subset C for each possible number of elements where len(B) = len(C) + 1. If for those subsets the property holds true then it holds true for any other subset. We should stop increasing the number of elements of B when the number of elements left in the set is less than B - 1.

Checking for the first property

To check for the first property is much harder, we can compare every possible combination of subsets of equal size and if it is true then the property applies to the set, but taking into account that this part of the problem is seen in depth in problem 106 I spend more time here to solve both problems at the same time.

The issue here is how to determine which are the combinations that are really needed to be checked and not spend checking combinations of subsets whose results wouldn't need to be calculated. For example in a set of length 4(0-index based) sorted, with subset B being the numbers in index 0, 2 and subset C being the numbers in index 1, 3; there's no need to check as every value in subset C is higher than one in subset B.

If we pay more attention to the example the key point is there. If there is at least a value in subset B that is higher than one is subset C then we can have an equality. If we have the combinations of all possible subsets to test it easy to determine which ones should be tested for equality and which ones can be discarded. That is, we will have two subsets of indexes of the set, if we sort them and pair them and for every pair the element is subset B is lower than in subset C then we won't need to check, otherwise we will need to check.

Code

from itertools import combinations, product, zip_longest
from functools import reduce
from math import ceil
 
d = {}
 
def filt_func(c1, c2):
    if c1[0] > c2[0]:
        return False
    return not reduce(lambda x, y: x and (y[0] < y[1]), zip_longest(sorted(c1), sorted(c2)), True)
 
def generator(n, k):
    if (n, k) in d:
        return d[(n, k)]
    s1 = combinations(range(n), k // 2)
    comb_total = []
    for comb1 in s1:
        left_nums = set(range(n)) - set(comb1)
        s2 = (c for c in combinations(left_nums, k // 2) if filt_func(comb1, c))
        comb_total.extend(product([comb1], s2))
    d[(n, k)] = comb_total
    return comb_total
 
def check_cond1(s):
    for i in range(4, len(s) + 1, 2):
        for c1, c2 in generator(len(s), i):
            if sum(map(lambda x: s[x], c1)) == sum(map(lambda x: s[x], c2)):
                return False
    return True
 
def check_cond2(s):
    for i in range(2, ceil(len(s) / 2) + 1):
        if sum(s[:i]) <= sum(s[-(i - 1):]):
            return False
    return True
 
if __name__ == '__main__':
    sets = []
    for l in open('sets.txt'):
        s = sorted(map(int, l.strip().split(',')))
        sets.append(s)
    result = sum(sum(s) for s in sets if check_cond2(s) and check_cond1(s))
    print("The result is:", result)

The Python file is available for download: problem105.py.