Project Euler

Special Subset Sums: Testing

Let S(A) denote 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 hold: 1. S(B)!= S(C); that is...

Source sync May 21, 2026

Problem #0105

Level Level 05

Solved By 9,400

Languages C++, Python

Answer 73702

Length 493 words

linear_algebrabrute_forceoptimization

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:

1.: $S(B) \ne S(C)$; that is, sums of subsets cannot be equal.
2.: If $B$ contains more elements than $C$ then $S(B) \gt 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_1, A_2, \dots , A_k$, and find the value of $S(A_1) + S(A_2) + \cdots + S(A_k)$.

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

Problem 105: Special Subset Sums: Testing

Mathematical Foundation

Theorem 1. (Equivalent Condition for Property 2) For a sorted set $A = \{a_1 < a_2 < \cdots < a_n\}$ , Property 2 holds if and only if for all $k = 1, 2, \ldots, \lfloor n/2 \rfloor$ :

\sum_{i=1}^{k+1} a_i > \sum_{i=n-k+1}^{n} a_i

Proof. ( $\Rightarrow$ ): Setting $B = \{a_1, \ldots, a_{k+1}\}$ and $C = \{a_{n-k+1}, \ldots, a_n\}$ in Property 2 gives the inequality directly, since $|B| = k+1 > k = |C|$ and $B \cap C = \emptyset$ (because $k+1 \leq n-k+1$ when $k \leq \lfloor n/2 \rfloor$ ).

( $\Leftarrow$ ): Let $B, C$ be disjoint subsets with $|B| = m > \ell = |C|$ . Write $B = \{b_1 < \cdots < b_m\}$ and $C = \{c_1 < \cdots < c_\ell\}$ . Since $b_i \geq a_i$ (the $i$ -th element of $B$ is at least the $i$ -th smallest in $A$ ) and $c_j \leq a_{n-\ell+j}$ (the $j$ -th element of $C$ is at most the $(n-\ell+j)$ -th smallest in $A$ ), we have:

S(B) \geq \sum_{i=1}^{m} a_i \geq \sum_{i=1}^{\ell+1} a_i > \sum_{i=n-\ell+1}^{n} a_i \geq S(C)

where the strict inequality uses the hypothesis with $k = \ell$ (valid since $\ell < m \leq n$ implies $\ell \leq \lfloor n/2 \rfloor$ when $B$ and $C$ are disjoint subsets of an $n$ -element set). $\square$

Theorem 2. (Subset Sum Uniqueness Implies Property 1) Property 1 (no two non-empty disjoint subsets have equal sums) holds if and only if all $2^n - 1$ non-empty subset sums are pairwise distinct.

Proof. ( $\Leftarrow$ ): Trivial, since disjoint subsets are in particular distinct subsets.

( $\Rightarrow$ ): Suppose for contradiction that two distinct non-empty subsets $B', C'$ satisfy $S(B') = S(C')$ . Let $D = B' \cap C'$ , $B = B' \setminus D$ , $C = C' \setminus D$ . Then $B \cap C = \emptyset$ and $B \cup C \neq \emptyset$ (since $B' \neq C'$ ). Moreover $S(B) = S(B') - S(D) = S(C') - S(D) = S(C)$ .

If $B = \emptyset$ , then $C' = D \cup C$ and $B' = D$ , so $S(D \cup C) = S(D)$ , giving $S(C) = 0$ . Since all elements are positive, this forces $C = \emptyset$ , contradicting $B \cup C \neq \emptyset$ . Similarly $C \neq \emptyset$ . Thus $B, C$ are non-empty, disjoint, with $S(B) = S(C)$ , violating Property 1. $\square$

Lemma 1. (Complexity Bound for Subset Enumeration) For a set of $n$ elements, the number of non-empty subsets is $2^n - 1$ . Checking distinctness of all subset sums can be done in $O(2^n)$ expected time using a hash set.

Proof. There are $2^n - 1$ non-empty subsets. We compute each subset sum incrementally (e.g., using Gray code enumeration, changing one element at a time, giving $O(1)$ per subset sum update). Inserting into and querying a hash set takes $O(1)$ expected time per operation. Total: $O(2^n)$ . $\square$

Editorial

Each set in the file is small enough that exhaustive subset work is feasible, but it is still worth rejecting bad sets as early as possible. After sorting a candidate set, the implementation first applies the size-ordering test from Theorem 1, which only compares a few sums of smallest and largest elements. If that condition fails, the set cannot possibly be special and no subset enumeration is needed.

Only sets that pass this quick filter are checked for distinct subset sums. At that point every non-empty subset is generated, its sum is inserted into a hash set, and the set is rejected immediately if a collision appears. The sums of all sets surviving both tests are then added together.

Pseudocode

Set the grand total to zero.

For each set in the input file:
    Sort the set.
    Check the size-ordering inequalities using the smallest and largest elements.
    If that test fails, discard the set immediately.
    Otherwise enumerate every non-empty subset and record each subset sum in a hash set.
    If a subset sum repeats, discard the set.
    If the set passes both tests, add the sum of its elements to the grand total.

Return the grand total.

Complexity Analysis

Time: $O(K \cdot 2^n)$ where $K = 100$ is the number of sets and $n \leq 12$ is the maximum set size. The Property 2 check is $O(n)$ per set and serves as a fast filter. The Property 1 check is $O(2^n)$ per set. In the worst case: $100 \cdot 2^{12} = 409{,}600$ operations.
Space: $O(2^n)$ for the hash set storing subset sums during Property 1 verification.

Answer

\boxed{73702}

C++ project_euler/problem_105/solution.cpp

#include <bits/stdc++.h>
using namespace std;

/*
 * Problem 105: Special Subset Sums: Testing
 *
 * For each of 100 sets (sizes 7-12), check:
 *   Condition 2: min-sum of (k+1)-subset > max-sum of k-subset
 *   Condition 1: all 2^n - 1 nonempty subset sums are distinct
 *
 * Sum S(A) for all passing sets.
 * Complexity: O(100 * 2^12) = O(409600).
 */

bool isSpecialSumSet(vector<int>& a) {
    int n = a.size();
    sort(a.begin(), a.end());

    // Condition 2: for k = 1..n/2, sum of first k+1 > sum of last k
    for (int k = 1; k <= n / 2; k++) {
        int sumLow = 0, sumHigh = 0;
        for (int i = 0; i <= k; i++) sumLow += a[i];
        for (int i = 0; i < k; i++) sumHigh += a[n - 1 - i];
        if (sumLow <= sumHigh) return false;
    }

    // Condition 1: all subset sums must be distinct
    set<int> sums;
    for (int mask = 1; mask < (1 << n); mask++) {
        int s = 0;
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) s += a[i];
        }
        if (sums.count(s)) return false;
        sums.insert(s);
    }
    return true;
}

int main() {
    // Try to read from file, fall back to stdin
    ifstream fin("p105_sets.txt");
    istream& in = fin.is_open() ? fin : cin;

    int total = 0;
    int specialCount = 0;
    string line;

    while (getline(in, line)) {
        if (line.empty()) continue;
        // Remove carriage return if present
        if (!line.empty() && line.back() == '\r') line.pop_back();
        replace(line.begin(), line.end(), ',', ' ');
        istringstream iss(line);
        vector<int> a;
        int x;
        while (iss >> x) a.push_back(x);
        if (a.empty()) continue;

        if (isSpecialSumSet(a)) {
            int s = 0;
            for (int v : a) s += v;
            total += s;
            specialCount++;
        }
    }

    assert(total == 73702);
    cout << total << endl;
    return 0;
}

Python project_euler/problem_105/solution.py

"""
Problem 105: Special Subset Sums: Testing

From a file of 100 sets, find those that are special sum sets
and compute the sum of their S(A) values.

A special sum set satisfies:
1. All subset sums are distinct.
2. Larger subsets have larger sums (size-ordering property).

Approach: For each set, check Condition 2 in O(n), then Condition 1 in O(2^n).
"""

import os
import urllib.request

# ---------------------------------------------------------------------------
# Core functions
# ---------------------------------------------------------------------------
def is_special_sum_set(a) -> bool:
    """Check if sorted list a is a special sum set."""
    a = sorted(a)
    n = len(a)

    # Condition 2: sum of first k+1 elements > sum of last k elements
    for k in range(1, n // 2 + 1):
        if sum(a[:k + 1]) <= sum(a[n - k:]):
            return False

    # Condition 1: all 2^n - 1 nonempty subset sums must be distinct
    sums = set()
    for mask in range(1, 1 << n):
        s = sum(a[i] for i in range(n) if mask & (1 << i))
        if s in sums:
            return False
        sums.add(s)

    return True

def is_special_brute(a) -> bool:
    """Brute-force: check all pairs of disjoint subsets."""
    a = sorted(a)
    n = len(a)
    for b in range(1, 1 << n):
        for c in range(b + 1, 1 << n):
            if b & c:  # not disjoint
                continue
            sb = sum(a[i] for i in range(n) if b & (1 << i))
            sc = sum(a[i] for i in range(n) if c & (1 << i))
            nb = bin(b).count('1')
            nc = bin(c).count('1')
            if sb == sc:
                return False
            if nb > nc and sb <= sc:
                return False
            if nc > nb and sc <= sb:
                return False
    return True

# ---------------------------------------------------------------------------
# Data loading
# ---------------------------------------------------------------------------
def get_data():
    local_file = os.path.join(os.path.dirname(os.path.abspath(__file__)), "p105_sets.txt")
    if os.path.exists(local_file):
        with open(local_file) as f:
            return f.read()
    url = "https://projecteuler.net/resources/documents/0105_sets.txt"
    try:
        response = urllib.request.urlopen(url)
        data = response.read().decode('utf-8')
        with open(local_file, 'w') as f:
            f.write(data)
        return data
    except Exception:
        raise RuntimeError("Could not download sets data. Place 'p105_sets.txt' locally.")

# ---------------------------------------------------------------------------
# Verify brute force matches optimized for small sets
# ---------------------------------------------------------------------------
test_sets = [
    [1, 2, 3, 5],       # special
    [1, 2, 3, 4],       # not special (1+4 = 2+3)
    [6, 9, 11, 12, 13], # special
]
for ts in test_sets:
    assert is_special_sum_set(ts) == is_special_brute(ts), f"Mismatch on {ts}"

# ---------------------------------------------------------------------------
# Main solve
# ---------------------------------------------------------------------------
def solve():
    data = get_data()
    total = 0
    special_sets = []

    for line in data.strip().split('\n'):
        line = line.strip()
        if not line:
            continue
        a = list(map(int, line.split(',')))
        if is_special_sum_set(a):
            s = sum(a)
            total += s
            special_sets.append((sorted(a), s))

    return total, special_sets

answer, special_sets = solve()
assert answer == 73702, f"Expected 73702, got {answer}"
print(answer)

# ---------------------------------------------------------------------------
# 4-Panel Visualization
# ---------------------------------------------------------------------------