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 Apr 19, 2026

Problem #0105

Level Level 05

Solved By 9,400

Languages C++, Python

Answer 73702

Length 436 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

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). We iterate over each set A in sets.

Pseudocode

for each set A in sets
if s in seen

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
# ---------------------------------------------------------------------------