Euler – Coder.si

Special subset sums: testing

Problem 105

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 (right click and "Save Link/Target As..."), 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).

NOTE: This problem is related to Problem 103 and Problem 106.

from tools import load_data_table_integers


def subsets(s, l):
    if l == 1:
        return [[d] for d in s]
    elif l == 0:
        return [[]]
    elif l < 0:
        return []
    subs = []
    for i in range(len(s)):
        for j in subsets(s[i + 1:], l - 1):
            subs.append([s[i]] + j)
    return subs


def check(s):
    lastsum = 0
    for i in range(1, len(s)):
        sums = set()
        for sub in subsets(s, i):
            subsum = sum(sub)
            if subsum in sums or subsum <= lastsum:
                return 0
            sums.add(subsum)
        lastsum = max(sums)
    return sum(s)


def run():
    data = load_data_table_integers(105, delimiter=',')
    return sum(check(s) for s in data)