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