Problem 105: Special Subset Sums: Testing

View on Project Euler

Project Euler Problem 105 Solution

EulerSolve provides an optimized solution for Project Euler Problem 105, Special Subset Sums: Testing, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary Each input line gives a finite set of positive integers. A candidate set \(A\) is a special sum set when every pair of non-empty disjoint subsets \(B, C \subseteq A\) satisfies both $$|B| \gt |C| \implies S(B) \gt S(C), \qquad S(B) \ne S(C),$$ where \(S(X)=\sum_{x\in X}x\). The task is purely a verification problem: test every listed set, keep the ones that satisfy both rules exactly, and add the total \(\sum_{a\in A} a\) of each accepted set. Mathematical Approach Write the set in increasing order as \(a_1 \lt a_2 \lt \cdots \lt a_n\). The implementations exploit two facts: the size comparison rule can be collapsed to a short prefix-versus-suffix test, while the equal-sum rule can be checked exactly by enumerating subsets and recording their sums. The two defining conditions The problem only cares about disjoint non-empty subsets. So the exact mathematical object being tested is the subset-sum map $$\sigma(X)=\sum_{x\in X} x,$$ restricted to pairs \(B,C\) with \(B\cap C=\varnothing\), \(B\ne\varnothing\), and \(C\ne\varnothing\). One rule compares sums when the subset sizes differ, and the other forbids equal sums for any disjoint pair at all....

Detailed mathematical approach

Problem Summary

Each input line gives a finite set of positive integers. A candidate set \(A\) is a special sum set when every pair of non-empty disjoint subsets \(B, C \subseteq A\) satisfies both

$$|B| \gt |C| \implies S(B) \gt S(C), \qquad S(B) \ne S(C),$$

where \(S(X)=\sum_{x\in X}x\). The task is purely a verification problem: test every listed set, keep the ones that satisfy both rules exactly, and add the total \(\sum_{a\in A} a\) of each accepted set.

Mathematical Approach

Write the set in increasing order as \(a_1 \lt a_2 \lt \cdots \lt a_n\). The implementations exploit two facts: the size comparison rule can be collapsed to a short prefix-versus-suffix test, while the equal-sum rule can be checked exactly by enumerating subsets and recording their sums.

The two defining conditions

The problem only cares about disjoint non-empty subsets. So the exact mathematical object being tested is the subset-sum map

$$\sigma(X)=\sum_{x\in X} x,$$

restricted to pairs \(B,C\) with \(B\cap C=\varnothing\), \(B\ne\varnothing\), and \(C\ne\varnothing\). One rule compares sums when the subset sizes differ, and the other forbids equal sums for any disjoint pair at all.

Reducing the size rule to prefix and suffix sums

Define

$$P_k=a_1+a_2+\cdots+a_k,\qquad Q_k=a_{n-k+1}+a_{n-k+2}+\cdots+a_n.$$

If a disjoint pair has sizes \(m+1\) and \(m\), then the smallest possible sum of the larger subset is \(P_{m+1}\), and the largest possible sum of the smaller subset is \(Q_m\). Therefore the rule

$$|B| \gt |C| \implies S(B) \gt S(C)$$

is guaranteed once

$$P_{m+1} \gt Q_m \qquad \text{for every } m \text{ with } 2m+1 \le n.$$

This is enough because any subset with more than \(m+1\) elements has an even larger sum, and the restriction \(2m+1 \le n\) is exactly the condition that disjoint subsets of sizes \(m+1\) and \(m\) can exist at all. So a potentially huge family of comparisons collapses to a short list of inequalities on the sorted set.

Exact disjoint-subset testing with bitmasks

For the second rule, each subset is encoded by a bitmask \(M \in \{1,\dots,2^n-1\}\). Its sum is

$$\sigma(M)=\sum_{i:\text{bit }i\text{ of }M\text{ is }1} a_{i+1}.$$

The exact condition checked by the implementations is

$$\sigma(M) \ne \sigma(N)\qquad \text{whenever } M \ne 0,\ N \ne 0,\ \text{and } M \mathbin{\&} N = 0.$$

That last bitwise condition is the disjointness test. It matters: equal sums coming from overlapping subsets are irrelevant here, so the implementation does not reject them. Only equal sums from disjoint subsets violate the definition.

A recurrence for subset sums

The C++ implementation fills all subset sums incrementally. If \(r\) is the position of the least significant set bit of \(M\), and \(M'=M\setminus\{r\}\), then

$$\sigma(M)=\sigma(M')+a_{r+1}.$$

This turns the table of all subset sums into a simple recurrence over masks. The Python and Java implementations compute the same mathematical quantity more directly, but the underlying object is identical: every non-empty subset gets a mask and a sum, and only disjoint masks are compared for collisions.

Worked example

Take \(A=\{3,5,6,7\}\). The size rule only needs one inequality because \(n=4\):

$$P_2=3+5=8,\qquad Q_1=7,\qquad 8 \gt 7.$$

So any disjoint 2-element subset already outweighs any 1-element subset, and positivity handles all larger size gaps automatically. The remaining task is to inspect disjoint subset sums. They are all different, so the set is accepted.

By contrast, \(A=\{2,3,4,5\}\) fails immediately because

$$P_2=2+3=5=Q_1,$$

so the size rule breaks. It also fails the equal-sum rule, since the disjoint subsets \(\{2,5\}\) and \(\{3,4\}\) both sum to \(7\). This illustrates why the implementations use a fast prefix-suffix filter first and the exact disjoint-mask check second.

How the Code Works

Sorting and the quick filter

The C++, Python, and Java implementations begin by sorting each candidate set. That produces the canonical order needed for the prefix and suffix inequalities. If any inequality \(P_{m+1} \gt Q_m\) fails, the set is rejected before any exhaustive subset work is done.

Enumerating subsets and checking disjoint collisions

After the quick filter, the implementation enumerates every non-empty subset. One version precomputes a full array of subset sums using the least-significant-bit recurrence, another generates combinations and builds the corresponding mask, and another scans all masks directly. Despite those surface differences, all three are doing the same exact test: for every pair of subset masks already seen, reject if the masks are disjoint and their sums coincide.

Accumulating the final total

If a candidate passes both tests, its element sum is added to a running total. The final output is the sum of the totals of all accepted special sum sets from the input list.

Complexity Analysis

For a set of size \(n\), sorting costs \(O(n \log n)\). The prefix-suffix filter is linear if prefix sums are stored explicitly and at worst quadratic in the direct summation style, which is still negligible compared with the exhaustive phase.

The exact verification handles \(2^n-1\) non-empty subsets, so the space usage is \(O(2^n)\) for the stored subset sums or mask-sum pairs. In the worst case, many subset pairs may need to be compared, giving \(O(4^n)\) time for the exact test. That sounds large asymptotically, but the published instances are small enough that exhaustive verification is practical, especially because many candidates are rejected by the prefix-suffix rule before the expensive phase begins.

Footnotes and References

  1. Problem page: Project Euler 105 - Special subset sums: testing
  2. Subset sum problem: Wikipedia - Subset sum problem
  3. Power set: Wikipedia - Power set
  4. Prefix sum: Wikipedia - Prefix sum

Problem 105 source code

C++

#include <algorithm>
#include <fstream>
#include <iostream>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>

namespace {

struct Options {
    std::string file = "resources/documents/0105_sets.txt";
    bool run_checkpoints = true;
};

bool parse_string_after_prefix(const std::string& arg,
                               const std::string& prefix,
                               std::string& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }
    value = tail;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_string_after_prefix(arg, "--file=", options.file)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return true;
}

bool satisfies_size_order_rule(const std::vector<int>& values) {
    const int n = static_cast<int>(values.size());
    std::vector<int> prefix(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        prefix[static_cast<std::size_t>(i + 1)] = prefix[static_cast<std::size_t>(i)] + values[static_cast<std::size_t>(i)];
    }

    for (int m = 1; 2 * m + 1 <= n; ++m) {
        const int left = prefix[static_cast<std::size_t>(m + 1)] - prefix[0];
        const int right = prefix[static_cast<std::size_t>(n)] - prefix[static_cast<std::size_t>(n - m)];
        if (left <= right) {
            return false;
        }
    }
    return true;
}

bool has_unique_disjoint_subset_sums(const std::vector<int>& values) {
    const int n = static_cast<int>(values.size());
    const int total_masks = 1 << n;
    std::vector<int> subset_sum(static_cast<std::size_t>(total_masks), 0);

    for (int mask = 1; mask < total_masks; ++mask) {
        const int bit = __builtin_ctz(static_cast<unsigned>(mask));
        const int prev = mask & (mask - 1);
        subset_sum[static_cast<std::size_t>(mask)] =
            subset_sum[static_cast<std::size_t>(prev)] + values[static_cast<std::size_t>(bit)];
    }

    for (int a = 1; a < total_masks; ++a) {
        for (int b = a + 1; b < total_masks; ++b) {
            if ((a & b) != 0) {
                continue;
            }
            if (subset_sum[static_cast<std::size_t>(a)] == subset_sum[static_cast<std::size_t>(b)]) {
                return false;
            }
        }
    }

    return true;
}

bool is_special_sum_set(std::vector<int> values) {
    std::sort(values.begin(), values.end());
    if (!satisfies_size_order_rule(values)) {
        return false;
    }
    if (!has_unique_disjoint_subset_sums(values)) {
        return false;
    }
    return true;
}

std::vector<int> parse_set_line(const std::string& line) {
    std::vector<int> values;
    std::istringstream input(line);
    std::string token;
    while (std::getline(input, token, ',')) {
        values.push_back(std::stoi(token));
    }
    return values;
}

int solve(const std::string& file_path) {
    std::ifstream input(file_path);
    if (!input) {
        throw std::runtime_error("Could not open sets file: " + file_path);
    }

    int total = 0;
    std::string line;
    while (std::getline(input, line)) {
        if (line.empty()) {
            continue;
        }
        const std::vector<int> values = parse_set_line(line);
        if (is_special_sum_set(values)) {
            for (int v : values) {
                total += v;
            }
        }
    }

    return total;
}

bool run_checkpoints() {
    if (!is_special_sum_set({3, 5, 6, 7})) {
        std::cerr << "Checkpoint failed: known special set rejected" << '\n';
        return false;
    }
    if (is_special_sum_set({2, 3, 4, 5})) {
        std::cerr << "Checkpoint failed: equal-sum disjoint subsets not detected" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    try {
        std::cout << solve(options.file) << '\n';
    } catch (const std::exception& ex) {
        std::cerr << ex.what() << '\n';
        return 3;
    }

    return 0;
}

Python

# Problem 105: Special subset sums: testing
# Sum all set values that satisfy the special subset sum conditions.

import os
from itertools import combinations

def is_special_sum_set(s):
    s = sorted(s)
    n = len(s)
    for k in range(1, n):
        if k + 1 <= n:
            if sum(s[:k+1]) <= sum(s[n-k:]):
                return False
    sums = {}
    for size in range(1, n+1):
        for combo in combinations(range(n), size):
            total = sum(s[i] for i in combo)
            mask = sum(1 << i for i in combo)
            for prev_mask, prev_sum in list(sums.items()):
                if prev_mask & mask == 0 and prev_sum == total:
                    return False
            sums[mask] = total
    return True

def solve():
    script_dir = os.path.dirname(os.path.abspath(__file__))
    file_path = os.path.join(script_dir, '..', 'resources', 'documents', '0105_sets.txt')
    total = 0
    with open(file_path) as f:
        for line in f:
            line = line.strip()
            if not line: continue
            values = list(map(int, line.split(',')))
            if is_special_sum_set(values):
                total += sum(values)
    print(total)

solve()

Java

import java.nio.file.*;
import java.util.*;

public class Euler105 {
    static boolean isSpecial(int[] s) {
        Arrays.sort(s);
        int n = s.length;
        for (int k = 1; k < n; k++) {
            int lo = 0, hi = 0;
            for (int i = 0; i <= k; i++)
                lo += s[i];
            for (int i = n - k; i < n; i++)
                hi += s[i];
            if (lo <= hi)
                return false;
        }
        Map<Integer, Integer> sums = new HashMap<>();
        for (int mask = 1; mask < (1 << n); mask++) {
            int sum = 0;
            for (int i = 0; i < n; i++)
                if ((mask & (1 << i)) != 0)
                    sum += s[i];
            for (Map.Entry<Integer, Integer> e : sums.entrySet())
                if ((e.getKey() & mask) == 0 && e.getValue() == sum)
                    return false;
            sums.put(mask, sum);
        }
        return true;
    }

    public static void main(String[] args) throws Exception {
        List<String> lines = Files.readAllLines(Path.of("resources/documents/0105_sets.txt"));
        int total = 0;
        for (String line : lines) {
            line = line.trim();
            if (line.isEmpty())
                continue;
            int[] vals = Arrays.stream(line.split(",")).mapToInt(Integer::parseInt).toArray();
            if (isSpecial(vals))
                total += Arrays.stream(vals).sum();
        }
        System.out.println(total);
    }
}