Solution

Answer: 73702

Let a set $A$ be sorted increasingly:

$$a_1 < a_2 < \cdots < a_n$$

We must test whether it is a special sum set, meaning:

No two distinct non-empty subsets have equal sums.
If one subset has more elements than another, then its sum must be larger.

The input file contains 100 candidate sets, each with $7$–$12$ elements. We must identify all valid special sum sets and sum their total set sums.

Mathematical analysis

Property 2: the fast necessary-and-sufficient check

Suppose the set is sorted.

If the smallest $k$ elements do not exceed the largest $k-1$ elements, then we could form:

a $k$-element subset with small sum,
a $(k-1)$-element subset with large sum,

violating condition (2).

Thus we require:

$$a_1 + a_2 + \cdots + a_k > a_n + a_{n-1} + \cdots + a_{n-k+2}$$

for every $k = 2,3,\dots,\lfloor n/2 \rfloor +1$.

This is enough because:

the smallest possible $k$-subset is the first $k$ elements,
the largest possible $(k-1)$-subset is the last $k-1$ elements.

So if even the smallest larger subset beats the largest smaller subset, then condition (2) always holds.

Property 1: uniqueness of subset sums

We must ensure:

$$S(B) \ne S(C)$$

for all distinct non-empty subsets $B,C$.

The brute-force approach works because the sets are tiny ($n \le 12$).

There are at most:

$$2^{12}=4096$$

subsets.

For each subset:

compute its sum,
store it in a set,
if the sum already appeared, property (1) fails.

This is computationally trivial.

Python implementation

from itertools import combinations
import urllib.request

URL = "https://projecteuler.net/resources/documents/0105_sets.txt"

# Download the file
data = urllib.request.urlopen(URL).read().decode()

sets_list = [
    list(map(int, line.split(",")))
    for line in data.strip().splitlines()
]

def satisfies_rule_2(nums):
    """
    Check:
    if |B| > |C| then S(B) > S(C)

    For a sorted list, it is sufficient to verify:
    sum(k smallest) > sum(k-1 largest)
    """
    nums = sorted(nums)
    n = len(nums)

    for k in range(2, n // 2 + 2):
        if sum(nums[:k]) <= sum(nums[-(k - 1):]):
            return False

    return True

def satisfies_rule_1(nums):
    """
    Check that all subset sums are unique.
    """
    n = len(nums)
    seen = set()

    # Enumerate all non-empty subsets
    for mask in range(1, 1 << n):
        subset_sum = 0

        for i in range(n):
            if mask & (1 << i):
                subset_sum += nums[i]

        if subset_sum in seen:
            return False

        seen.add(subset_sum)

    return True

def is_special_sum_set(nums):
    return satisfies_rule_2(nums) and satisfies_rule_1(nums)

answer = 0

for s in sets_list:
    if is_special_sum_set(s):
        answer += sum(s)

print(answer)

Code walkthrough

Reading the file

data = urllib.request.urlopen(URL).read().decode()

Downloads the text file directly.

Each line becomes one integer set:

sets_list = [
    list(map(int, line.split(",")))
    for line in data.strip().splitlines()
]

Checking Rule 2

nums = sorted(nums)

Sorting is essential.

For each $k$:

sum(nums[:k])

computes the sum of the $k$ smallest elements.

And:

sum(nums[-(k - 1):])

computes the sum of the $(k-1)$ largest elements.

If:

<=

then condition (2) fails immediately.

Checking Rule 1

We enumerate all subsets via bitmasks:

for mask in range(1, 1 << n):

If bit $i$ is set, element $i$ belongs to the subset.

Each subset sum is inserted into seen.

If a duplicate appears:

if subset_sum in seen:
    return False

then two distinct subsets share the same sum.

Example verification

The set:

$${81,88,75,42,87,84,86,65}$$

fails because:

$$65+87+88 = 75+81+84$$

so Rule 1 fails.

The set:

$${157,150,164,119,79,159,161,139,158}$$

passes both rules, giving:

$$157+150+164+119+79+159+161+139+158 = 1286$$

matching the problem statement.

Final verification

Only 100 sets are tested.
Each has at most 4095 non-empty subsets.
Runtime is tiny.
The resulting total is positive and of reasonable magnitude for ~100 medium-sized sets.

The computed total is:

Answer: 73702

Project Euler Problem 105