Problem 105: Special Subset Sums: Testing

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

For a set $A$ of $n$ numbers, let $S(A)$ be the sum of its elements. The set is called a special sum set if any two non-empty disjoint subsets $B$ and $C$ of $A$, that is, subsets with no element in common, obey two rules:

rule 1: $S(B)\ne S(C)$, so two disjoint subsets never have the same sum;
rule 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} obeys both rules for every pair of subsets and has $S(A)=1286$. The text file sets.txt, about 4 kilobytes long, lists one hundred sets with seven to twelve elements each, one set per line, and the two examples are its first two sets. We must identify all special sum sets $A_1,\dots,A_k$ in the file and find $S(A_1)+S(A_2)+\dots+S(A_k)$. ^[1] The statement adds that the problem is related to Problem 103, which looks for special sum sets with the smallest possible sum, ^[2] and to Problem 106, which asks how many pairs of subsets really have to be tested. ^[3]

The whole solution in one sentence: after a set is sorted, rule 2 needs only a handful of comparisons (the two smallest elements against the largest one, the three smallest against the two largest, and so on), and rule 1 is checked by computing the sums of all $2^n$ subsets and comparing every two subsets that share no element; the element sums of the sets that pass both tests are added up. The sections below prove that these tests are exactly right, starting from sets small enough to check by hand.

Mathematical Approach

We first try the two rules on tiny sets and count how much work a direct check needs. Then we prove two facts that make the check short and safe: rule 2 can be decided by looking only at the smallest and the largest elements, and, for positive numbers, rule 1 says the same as "all subset sums are different".

1. Two rules, tried on tiny sets

A set with one element has no two non-empty disjoint subsets at all, so it is special. A set $\{a,b\}$ has a single pair, $\{a\}$ against $\{b\}$; rule 1 holds because $a\ne b$, and rule 2 has nothing to say, so every set with two elements is special as well. With three elements the rules start to bite. In $\{1,2,3\}$ the subsets $B=\{1,2\}$ and $C=\{3\}$ have no element in common and the same sum $3$, so rule 1 fails; and $B$ has more elements than $C$ without having a larger sum, so rule 2 fails too.

Now take $\{2,3,4\}$. There are six ways to choose two non-empty disjoint subsets, and we can list all of them with their sums:

one element against one element: $2$ and $3$, $2$ and $4$, $3$ and $4$;
one element against the other two: $2$ and $3+4=7$, $3$ and $2+4=6$, $4$ and $2+3=5$.

In every pair the two sums differ, so rule 1 holds, and in the three pairs of the second line the subset with two elements has the larger sum, so rule 2 holds as well: $\{2,3,4\}$ is a special sum set. Problem 103 lists it as the special sum set with three elements whose sum is as small as possible. ^[2]

The two rules are independent of each other, so a program must check both. In $\{1,2,4\}$ the eight subset sums are $0,1,2,\dots,7$, each exactly once, just as every number from $0$ to $7$ has exactly one binary representation with the place values $1$, $2$ and $4$. So rule 1 holds, but $1+2=3$ is smaller than $4$, and rule 2 fails. In $\{4,5,6,7\}$ any two elements add up to at least $9$ and any three to at least $15$, more than any single element, so rule 2 holds; but $4+7=5+6=11$, and rule 1 fails.

2. How many pairs of subsets there are

A direct check looks at every pair of non-empty disjoint subsets. To count these pairs, decide for every element whether it goes into $B$, into $C$ or into neither: that makes $3^n$ choices. Of them, $2^n$ leave $B$ empty, namely those in which every element goes into $C$ or into neither, and another $2^n$ leave $C$ empty. The single choice that puts every element into neither leaves both empty, so it has been subtracted twice and is added back once; this is the inclusion–exclusion principle for two sets. ^[4] Finally, the pair $B$, $C$ is the same pair as $C$, $B$, so we divide by $2$:

$$\frac{3^n-2\cdot2^n+1}{2}=\frac{3^n-2^{n+1}+1}{2}.$$

For $n=3$ this gives $(27-16+1)/2=6$, the six pairs of Section 1. For $n=4$, $7$ and $12$ it gives $25$, $966$ and $261\,625$, the numbers quoted in the statement of Problem 106. ^[3] A computer gets through a quarter of a million pairs in a moment, so a direct check is possible for the sets of this problem, but the count almost triples with every new element. The next sections cut the work down, first for rule 2 and then for rule 1.

3. Sorting, and the lightest and heaviest subsets

Neither rule depends on the order in which the elements are listed, so we may sort them: $a_1\lt a_2\lt\dots\lt a_n$. The order is strict because the elements of a set are all different. For $k\le n$ let

$$\begin{aligned}P_k&=a_1+a_2+\dots+a_k,\\Q_k&=a_{n-k+1}+\dots+a_{n-1}+a_n\end{aligned}$$

be the sum of the $k$ smallest and the sum of the $k$ largest elements. For $\{2,3,4\}$, for instance, $P_2=5$ and $Q_2=7$, and the three subsets with two elements have the sums $5$, $6$ and $7$, all between these two numbers. This is no accident.

Lemma. Every subset $B$ with $k$ elements satisfies $P_k\le S(B)\le Q_k$.

Proof. Write the elements of $B$ in increasing order, $b_1\lt b_2\lt\dots\lt b_k$. The $j$ elements $b_1,\dots,b_j$ of $A$ are all at most $b_j$, so $b_j$ is at least the $j$-th smallest element of $A$: $b_j\ge a_j$. Adding these $k$ inequalities gives $S(B)\ge P_k$. In the same way the $j$-th largest element of $B$ is at most the $j$-th largest element of $A$, and adding gives $S(B)\le Q_k$.

4. Rule 2 needs only a few comparisons

If $2k+1\le n$, the $k+1$ smallest and the $k$ largest elements do not overlap, so rule 2 demands $P_{k+1}\gt Q_k$: the lightest subset with $k+1$ elements must still be heavier than the heaviest subset with $k$ elements. The pleasant surprise is that these few comparisons are also enough.

Theorem. A set obeys rule 2 exactly when

$$P_{k+1}\gt Q_k\qquad\Bigl(1\le k\le\frac{n-1}{2}\Bigr).$$

Proof. We have just seen that rule 2 implies these inequalities. For the converse, assume them. If $n\le2$ there is nothing to prove, because two non-empty disjoint subsets of different sizes need at least $1+2=3$ elements. If $n\ge3$, the inequality for $k=1$ says $a_1+a_2\gt a_n\ge a_2$, so $a_1\gt0$, and every element is positive. Now let $B$ and $C$ be non-empty and disjoint, with $c$ elements in $C$ and more than $c$ in $B$. Keep only the $c+1$ smallest elements of $B$ and call this subset $B'$. Removing positive elements lowers a sum, so $S(B)\ge S(B')$. The subsets $B'$ and $C$ are disjoint, so $(c+1)+c\le n$, and the inequality for $k=c$ is one of those we assumed. With the lemma of Section 3,

$$\begin{aligned}S(B)&\ge S(B')\ge P_{c+1}\\&\gt Q_c\ge S(C).\end{aligned}$$

So a set with $n$ elements needs only $\lfloor(n-1)/2\rfloor$ comparisons for rule 2, that is, $(n-1)/2$ rounded down: one for $n=3$ or $n=4$, and five for $n=12$, where $224\,731$ of the $261\,625$ pairs have subsets of different sizes (Section 9 counts the $36\,894$ pairs of equal size, and $261\,625-36\,894=224\,731$). Positivity is a real ingredient of the proof, because without it removing elements from $B$ could raise the sum. Here it comes for free, since the comparison for $k=1$ forces it, and every number in the file is positive anyway.

5. The two sets of the statement

Sorted, the first example set of the statement reads 42, 65, 75, 81, 84, 86, 87, 88. With $n=8$ there are three comparisons: $42+65=107\gt88$, then $P_3=182\gt175=Q_2$, and $P_4=263\gt261=Q_3$. So this set obeys rule 2, and by the theorem it does so for all of its pairs of subsets. Yet it is not special: $65+87+88$ and $75+81+84$ are both $240$, and rule 1 fails.

The second example set, sorted, is 79, 119, 139, 150, 157, 158, 159, 161, 164. Its four comparisons are $198\gt164$, $337\gt325$, $487\gt484$ and $644\gt642$, so it obeys rule 2, with margins $34$, $12$, $3$ and $2$ that shrink from one comparison to the next. Whether it also obeys rule 1 is the subject of the next section.

6. Equal sums: disjoint subsets and all subsets

Rule 1 speaks only about disjoint subsets, but for positive numbers, overlapping subsets with equal sums always hide a disjoint pair. In the first example set, the elements 42 and 86 take no part in the equal sums $65+87+88=75+81+84$. Adding the same extra elements to both sides keeps the sums equal: adding 42 gives two subsets with the sum $282$, adding 86 gives two with $326$, and adding both gives two with $368$. Going backwards, removing the common elements of two subsets with equal sums leaves two disjoint subsets with equal sums.

Claim. For a set of positive numbers, rule 1 holds exactly when all $2^n$ subsets, the empty one included, have different sums.

Proof. If all subset sums differ, then in particular two disjoint non-empty subsets, which are two different subsets, have different sums. Conversely, suppose that two different subsets $X$ and $Y$ have the same sum, and remove their common part: $B=X\setminus Y$ and $C=Y\setminus X$ are disjoint, and

$$\begin{aligned}S(B)&=S(X)-S(X\cap Y)\\&=S(Y)-S(X\cap Y)=S(C).\end{aligned}$$

They are not both empty, since $X\ne Y$. If one of them were empty, the other would be a non-empty set of positive numbers with the sum $0$, which is impossible. So $B$ and $C$ break rule 1.

A computer confirms the example: among the $256$ subsets of the first set exactly four sums occur twice, $240$, $282$, $326$ and $368$, and all four come from the one disjoint pair of the statement, which is the only disjoint pair with equal sums in this set. The $512$ subsets of the second set, on the other hand, have $512$ different sums, so it obeys rule 1, and with Section 5 it is a special sum set. For the positive numbers of this problem, the claim also shows that a program which compared all pairs of different subsets, overlapping or not, would reach exactly the same verdicts; the published programs test disjointness because that is how the rule is worded.

7. Subsets as binary numbers

To let a program walk through all subsets, number the sorted elements $0,1,\dots,n-1$, so that element number $i$ is $a_{i+1}$, and describe a subset by an $n$-digit binary number, its mask, whose digit in place $i$, counting from the right and starting at $0$, is $1$ when element number $i$ belongs to the subset. The masks $0,1,\dots,2^n-1$ describe the $2^n$ subsets, each exactly once; this is also why the power set, the set of all subsets, of a set with $n$ elements has $2^n$ members. ^[6] For $\{3,5,6,7\}$, the mask $13=8+4+1$, written $1101_2$ in binary, has ones in the places $0$, $2$ and $3$ and stands for $\{3,6,7\}$, with the sum $16$.

Two subsets are disjoint exactly when their masks never have a $1$ in the same place, that is, when the bitwise AND of the masks, which has a $1$ only where both masks have one, is $0$. The mask $2=0010_2$, the subset $\{5\}$, and $1101_2$ give the AND $0000_2$: the two subsets are disjoint. The mask $5=0101_2$, the subset $\{3,6\}$, and $1101_2$ give the AND $0101_2$: the two subsets share the elements $3$ and $6$.

The empty subset has the sum $0$, and every other subset sum can be found with one addition. Subtracting $1$ from a mask turns its lowest $1$ into $0$ and the zeros below it into ones, so the AND of a mask $x$ with $x-1$ is $x$ with its lowest $1$ removed. If that lowest $1$ is in place $i$, the subset of $x$ is the subset of the smaller mask together with element number $i$, so its sum is the smaller mask's sum plus that element. For example, $12=1100_2$ has its lowest $1$ in place $2$, and $12-1=11=1011_2$ gives the AND $1000_2=8$. The sum for the mask $12$, the subset $\{6,7\}$, is therefore the sum $7$ for the mask $8$ plus element number $2$, which is $6$, so it is $13$. The smaller mask always comes earlier, so a single pass through the masks in increasing order fills the whole table of $2^n$ sums.

8. A complete example: $\{3,5,6,7\}$

Problem 103 lists $\{3,5,6,7\}$ as the special sum set with four elements and the smallest sum, $21$. ^[2] The two tests confirm that it is special. Rule 2: for $n=4$ the theorem of Section 4 needs only $k=1$, and $P_2=3+5=8$ is larger than $Q_1=7$. Rule 1: the $16$ subset sums, in increasing order, are

$0,3,5,6,7,8,9,10,$
$11,12,13,14,15,16,18,21.$

They are all different, so by Section 6 no two disjoint subsets have equal sums. Both rules hold, and $\{3,5,6,7\}$ is special. The C++ program uses exactly this set as its first self-check.

The set $\{2,3,4,5\}$ fails in both ways. Rule 2 fails at its only comparison, since $P_2=2+3=5$ is not larger than $Q_1=5$. Its subset sums contain $5$, $7$ and $9$ twice each: $\{5\}$ and $\{2,3\}$, then $\{2,5\}$ and $\{3,4\}$, and finally $\{4,5\}$ and $\{2,3,4\}$. The last two share the element $4$, and removing it leaves the first pair, exactly as in Section 6.

9. Once rule 2 holds, only equal sizes can collide

If a set obeys rule 2, two disjoint subsets of different sizes never have equal sums, because the larger subset has the larger sum. So rule 1 only has to be checked for pairs of subsets of the same size $k$. To count these pairs we use the binomial coefficient $\binom nk$, read "$n$ choose $k$", the number of ways to choose $k$ of $n$ elements when the order does not matter; for example, $\binom42=6$, since two of four elements can be chosen in six ways. ^[15] Choosing $B$ in $\binom nk$ ways and then $C$ among the remaining $n-k$ elements in $\binom{n-k}k$ ways counts every such pair twice, once in each order. The two subsets use $2k$ elements together, so $k$ runs from $1$ to $\lfloor n/2\rfloor$, and there are

$$\frac12\sum_{k=1}^{\lfloor n/2\rfloor}\binom nk\binom{n-k}k$$

of them: $9$ of the $25$ pairs for $n=4$, and $36\,894$ of the $261\,625$ pairs for $n=12$. Many of these cannot collide either. Two subsets with one element each have different sums, because the elements are different. More generally, if the sorted elements of $B$ and $C$ satisfy $b_j\lt c_j$ for every $j$, then adding these inequalities gives $S(B)\lt S(C)$. For $n=4$ this settles eight of the nine pairs: the six pairs of single elements, $\{a_1,a_2\}$ against $\{a_3,a_4\}$, because $a_1\lt a_3$ and $a_2\lt a_4$, and $\{a_1,a_3\}$ against $\{a_2,a_4\}$, because $a_1\lt a_2$ and $a_3\lt a_4$. Only $\{a_1,a_4\}$ against $\{a_2,a_3\}$ really needs a test, because $a_1\lt a_2$ but $a_4\gt a_3$; it is exactly the pair that fails in $\{4,5,6,7\}$. Problem 106 counts the pairs that need a test: $1$ of $25$ for $n=4$ and $70$ of $966$ for $n=7$. ^[3] The published programs do not use these savings; they test every disjoint pair, which is fast enough for twelve elements.

10. A faster test for rule 1

By Section 6, rule 1 asks whether the $2^n$ subset sums are all different. This is the element distinctness problem, and the classic solution is to sort the numbers and compare neighbours, since equal numbers end up next to each other; a hash table, which files every number under a key computed from it, does the same job in expected linear time, that is, with on average a fixed amount of work per number. ^[9] Merge sort, for example, splits a list into two halves, sorts each half in the same way and merges the two sorted halves; a merge needs fewer comparisons than there are numbers, because each comparison moves one number into place and the last one needs none. ^[14] For the $4096=2^{12}$ subset sums of a set with twelve elements the splitting goes $12$ levels deep, and each level of merges costs fewer than $4096$ comparisons, so sorting takes fewer than $12\cdot4096=49\,152$ comparisons. In general, sorting $N$ numbers takes about $N\log_2N$ comparisons, and no method that only compares numbers can decide whether they are all different with essentially fewer. ^[9] The published loops, in contrast, visit all $4095\cdot4094/2=8\,382\,465$ pairs of non-empty masks of a special set with twelve elements, $261\,625$ of them disjoint.

The same view gives a quick necessary condition. For a set of positive whole numbers, all $2^n$ subset sums are whole numbers from $0$ to $S(A)$. If they are all different, there must be at least $2^n$ such numbers, so $S(A)\ge2^n-1$; otherwise two subsets share a sum by the pigeonhole principle. ^[7] For $n=12$ this demands $S(A)\ge4095$. Every set in the file passes this test, the closest one with $151$ to spare, so here it saves no work. Sets whose subset sums are all different are called dissociated, and how small the largest element of such a set can be is Problem 1 on the Erdős problems website, a question that Erdős called perhaps his first serious problem. The counting argument above gives a lower bound for that largest element: $S(A)$ is at most $n$ times the largest element, so the largest element is at least $(2^n-1)/n$, roughly $2^n/n$. For $n=12$ that is $4095/12=341.25$, so the largest element is at least $342$. ^[8]

11. The hundred sets of the file

The file has one hundred lines with one set each: $11$ sets with seven elements, $20$ with eight, $23$ with nine, $20$ with ten, $16$ with eleven and $10$ with twelve. All numbers are positive whole numbers between $20$ and $1287$, and no line repeats a number. Running the two tests in order gives this picture:

$13$ sets fail rule 2. The size test rejects $2$ of them at the comparison for $k=2$, $4$ first at $k=3$, $4$ first at $k=4$ and $3$ first at $k=5$, and none at $k=1$; the two sets rejected at $k=2$ fail the comparison for $k=3$ as well. Three of these $13$ sets have all their subset sums different, so they would pass rule 1 on its own.
Of the remaining $87$ sets, $59$ contain two disjoint subsets with equal sums, just like the first example set of the statement.
The other $28$ sets are special sum sets, and the requested number is the sum of their element sums.

How the Code Works

The C++ program ^[13] starts in main with an Options record that holds the input file, resources/documents/0105_sets.txt relative to the working directory, and a flag for the self-checks. parse_arguments accepts --skip-checkpoints and --file= followed by a path, and the program stops with exit code 1 on any other argument. Unless the checks are skipped, run_checkpoints then demands that $\{3,5,6,7\}$ is accepted and $\{2,3,4,5\}$ rejected, and the program stops with exit code 2 otherwise.

solve opens the file, reads it line by line, skips empty lines and lets parse_set_line split each line at the commas and convert the pieces with std::stoi. is_special_sum_set receives its own copy of the numbers, sorts it and applies the two tests in the order of the mathematics. satisfies_size_order_rule first builds the prefix sums, the running totals prefix[i] of the first $i$ sorted elements, ^[5] so that the sum of any run of consecutive elements is the difference of two of them. For $m=1,2,\dots$ as long as $2m+1\le n$, it compares prefix[m + 1] - prefix[0], which is $P_{m+1}$, with prefix[n] - prefix[n - m], which is $Q_m$, and rejects the set as soon as the first is not larger. This is the theorem of Section 4.

Only sets that pass reach has_unique_disjoint_subset_sums. It fills the vector subset_sum with $2^n$ entries in one pass over the masks, exactly as in Section 7: __builtin_ctz(mask), a GCC built-in function that counts the zero bits below the lowest $1$, ^[10] gives the place of the new element, and mask & (mask - 1) gives the smaller mask. The built-in is undefined for $0$, but the loop starts at the mask $1$, so it never sees $0$. Then two nested loops run over all masks a from $1$ to $2^n-1$ and all masks b above a. A pair whose AND is not $0$ is skipped, and a disjoint pair with equal sums ends the test with false. If the test runs to the end, every unordered pair of non-empty disjoint subsets, the pairs counted in Section 2, is compared exactly once, but to find them the loops visit all $(2^n-1)(2^n-2)/2$ pairs of non-empty masks. The program adds the elements of every accepted set to an int named total and prints it. If the file cannot be opened, solve throws an exception, and main reports it and returns 3.

The second self-check tests less than its error message suggests. The message speaks of equal-sum disjoint subsets, but $\{2,3,4,5\}$ is already rejected by the size test, since $2+3=5$, so this check never reaches has_unique_disjoint_subset_sums. A set such as $\{4,5,6,7\}$, which passes the size test and fails only rule 1, would exercise that stage too.

The Python version has the same two stages in is_special_sum_set, without self-checks or options. Its size test lets $k$ run from $1$ to $n-1$ and compares sum(s[:k+1]) with sum(s[n-k:]); the extra condition k + 1 <= n is always true. For $2k+1\gt n$ the two slices overlap. After the shared elements are cancelled, the comparison becomes the one for $n-k-1$, which the loop has already made, or, for $k=n-1$, the test $a_1\gt0$, so the extra rounds never change the verdict for positive numbers. For example, for $n=5$ and $k=3$ the loop compares $a_1+a_2+a_3+a_4$ with $a_3+a_4+a_5$; cancelling $a_3$ and $a_4$ leaves $a_1+a_2$ against $a_5$, the comparison for $k=1$. The second stage visits the subsets by size with itertools.combinations(range(n), size), which produces the positions in lexicographic order, builds each mask as a sum of powers of two, and compares the new subset with every subset stored so far in the dictionary sums, which maps masks to sums, before storing it. The scan runs over list(sums.items()), a fresh list of all mask–sum entries of the dictionary, made for every new subset; the list is not needed, since the dictionary changes only after the scan, so scanning sums.items() directly would give the same verdicts. The test prev_mask & mask == 0 means "the AND is $0$", because in Python every comparison binds more loosely than the bitwise operators, unlike in C. ^[11] The file is found relative to the script's own folder, one level up and then in resources/documents.

The Java version follows the Python one. isSpecial sorts the array in place with Arrays.sort, which does no harm because afterwards only the sum of the elements is used, runs the same size test with two inner loops, and then goes through the masks from $1$ to $2^n-1$ in increasing order. It computes each sum by testing all $n$ bits and compares it with every entry of a HashMap<Integer, Integer> from masks to sums. Here the parentheses in (e.getKey() & mask) == 0 are required, because in Java == binds more tightly than &. The comparison e.getValue() == sum puts a boxed Integer next to an int; the Java Language Specification then unboxes the object and compares two numbers, while two Integer objects would be compared as objects. ^[12] main reads all lines of resources/documents/0105_sets.txt relative to the working directory, trims them, skips empty ones and adds up the special sets in an int.

Complexity and Verification

For a set with $n$ elements, sorting and the size test cost almost nothing. The C++ size test builds the prefix sums with $n$ additions and then makes at most $\lfloor(n-1)/2\rfloor$ comparisons. The Python and Java versions make at most $n-1$ comparisons but add up both groups anew for each, $2k+1$ numbers in round $k$, so a set that passes costs them $n^2-1$ additions, $143$ for $n=12$. The second stage dominates. In C++ a table of $2^n$ subset sums is filled first: the entry of the empty subset is $0$, and each of the other $2^n-1$ entries takes one addition. Python and Java compute the sum of each subset in about $n$ steps just before using it, and store it only after comparing it with the sums stored so far. In all three versions the comparisons take up to $(2^n-1)(2^n-2)/2$ steps, about $2^{2n-1}$: for $n=12$ that is $8\,382\,465$ steps, $261\,625$ of them on disjoint pairs. A set that breaks rule 1 leaves the loops early, but a special set has to be checked completely. So the time per set grows like $4^n$ and the memory like $2^n$; sorting the subset sums as in Section 10 would bring the time down to about $n\,2^n$. The list of entries that Python builds before each scan handles every stored entry once more; leaving it out made the Python test of the hundred sets about $40\%$ faster in a measurement with CPython 3.11, but the time would still grow like $4^n$.

A copy of the C++ program with counters added shows the real amount of work on the file: $87$ sets reach the second stage, the inner loop runs $31\,876\,506$ times, and $2\,097\,843$ of these steps compare the sums of two disjoint subsets. The $28$ special sets alone account for $21\,009\,372$ loop steps. Each of the $59$ sets rejected in the second stage is left, on average over these sets, after about a fifth of its pairs of masks; together they use $10\,867\,134$ of their $96\,093\,627$ possible loop steps, about one ninth. On a current desktop computer, start-up included, the C++ program needs one to three hundredths of a second, depending on the compiler options, the Java version about $0.2$ seconds and the Python version just under one second; such times vary between machines, while the loop counts above do not. C++ and Java keep all sums in 32-bit int variables, while Python's integers never overflow; here this makes no difference, because the largest element sum of a set in the file is $13\,549$, so even the total of all one hundred sets is below $1.4\cdot10^6$, far inside the range of a 32-bit int.

The C++ program checks itself with the two sets of Section 8 before it reads the file. For this article more was verified separately, and none of the following is part of the published solutions. All three programs print the same number. An independent program applied the definition directly: for every set of the file it went through all $3^n$ ways of putting each element into $B$, into $C$ or into neither, without sorting, prefix sums or a table of subset sums, and it found the same $28$ special sets and the same total. The theorem of Section 4, the claim of Section 6 and the longer size loop of the Python and Java versions were compared with the definition on all $8191$ non-empty subsets of $\{1,\dots,13\}$ and on $20\,000$ random sets of up to eight positive numbers up to $1000$, without a single disagreement. The count of Section 2 and the count of equal-size pairs in Section 9 agree with a direct listing of the pairs for every $n\le12$, and the test of Section 9 that compares sorted elements reproduces the numbers $1$ of $25$ and $70$ of $966$ from Problem 106.

Footnotes and References

The references below supply the background facts used above. The reduction of rule 2 to a few comparisons, the equivalence of rule 1 with distinct subset sums, the counts of pairs and the statistics of the file are derived or computed explicitly in this article.

Project Euler 105 — Special Subset Sums: Testing. The official statement defines S(A) and special sum sets by the two rules for any two non-empty disjoint subsets B and C, shows that {81, 88, 75, 42, 87, 84, 86, 65} is not special because 65 + 87 + 88 = 75 + 81 + 84 and that {157, 150, 164, 119, 79, 159, 161, 139, 158} is special with S(A) = 1286, and asks for S(A₁) + S(A₂) + … + S(Aₖ) over the special sum sets among the one hundred sets of seven to twelve elements in the file sets.txt.
Project Euler 103 — Special Subset Sums: Optimum. A special sum set is called optimum when S(A) is as small as possible for its size n; the statement lists the optimum sets {1}, {1, 2}, {2, 3, 4}, {3, 5, 6, 7} and {6, 9, 11, 12, 13} for n = 1 to 5.
Project Euler 106 — Special Subset Sums: Meta-testing. The statement considers a set of n strictly increasing elements that already satisfies the second rule and observes that for n = 4 only 1 of the 25 subset pairs needs to be tested for equality, and for n = 7 only 70 of the 966 pairs; for n = 12 it speaks of 261625 subset pairs.
Wikipedia — Inclusion–exclusion principle. For two finite sets, |A ∪ B| = |A| + |B| − |A ∩ B|: adding the two sizes counts the elements of the intersection twice, so the size of the intersection is subtracted once. Section 2 applies this to the choices in which B or C is empty.
Wikipedia — Prefix sum. The prefix sums of a sequence are the sums of its prefixes, that is, its running totals; the C++ size test keeps them in the vector prefix.
Wikipedia — Power set. A set with n elements has 2ⁿ subsets, and the page's section "Representing subsets as functions" writes the subsets of a finite set as binary numbers in which every element has a fixed bit position and a 1 means that the element belongs to the subset, like the masks of Section 7.
Wikipedia — Pigeonhole principle. If n items are put into m containers with n > m, then at least one container holds more than one item; Section 10 applies this to the 2ⁿ subset sums and the S(A) + 1 possible values 0, 1, …, S(A).
Erdős Problems — Problem 1. The problem concerns sets of n integers in {1, …, N} whose subset sums are all distinct and asks whether N must be at least a constant multiple of 2ⁿ. The page notes that Erdős called it perhaps his first serious problem, calls such sets dissociated, and records the trivial lower bound of order 2ⁿ/n, which holds because all 2ⁿ distinct subset sums lie in [0, nN], an interval with only nN + 1 whole numbers.
Wikipedia — Element distinctness problem. Deciding whether all elements of a list are distinct can be done by sorting the list and checking for consecutive equal elements, or in linear expected time by a randomised algorithm that places the items in a hash table. For algorithms that compare elements, every solution needs on the order of n log n comparisons, and sorting meets this bound up to a constant factor.
GCC manual — Bit Operation Builtins. __builtin_ctz(x) returns the number of trailing 0-bits in x, starting at the least significant bit position, and the result is undefined if x is 0.
Python — itertools.combinations emits the combinations in lexicographic order according to the order of the input and treats elements as unique by their position. Python — Comparisons states that, unlike in C, all comparison operations in Python have the same priority, which is lower than that of any arithmetic, shifting or bitwise operation.
The Java Language Specification, Java SE 17, §15.21.1 — Numerical Equality Operators. If one operand of == is of numeric type and the other is convertible to numeric type, binary numeric promotion, which may include unboxing, is performed, and an integer equality test follows for int operands. §15.21.3 on the same page adds that two operands of reference type are compared as objects: == is true only if both refer to the same object. In §15.22 the operands of & are equality expressions, so == binds more tightly than &.
C++ — Euler105.cpp. The linked immutable C++ revision contains satisfies_size_order_rule, has_unique_disjoint_subset_sums, run_checkpoints and the options --skip-checkpoints and --file=. It is the implementation record for this article.
Wikipedia — Merge sort. Merge sort repeatedly merges sorted sublists until one list is left; for n objects it makes at most n⌈lg n⌉ − 2^⌈lg n⌉ + 1 comparisons, with lg the logarithm to base 2, which is 45057 for n = 4096.
Wikipedia — Binomial coefficient. The binomial coefficient of n and k, usually read "n choose k", is the number of ways to choose an unordered subset of k elements from a fixed set of n elements; the page's example counts the 6 ways to choose 2 elements from {1, 2, 3, 4}. Section 9 uses it to count the pairs of subsets of equal size.

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);
    }
}