Problem 103: Special Subset Sums: Optimum

Project Euler Problem 103 Solution

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

Problem Summary We seek an increasing seven-element set $A=\{a_1,a_2,\dots,a_7\}$ of positive integers with the smallest possible total sum such that two conditions hold. First, no two non-empty disjoint subsets of $A$ may have the same sum. Second, whenever two disjoint subsets have different sizes, the larger subset must also have the larger sum. The optimum set is $\{20,31,38,39,40,42,45\}$, so the required concatenated string is $20313839404245$. The supplied implementations do not use a closed-form formula. Instead, they combine a sharp structural lemma for the size condition, an explicit disjoint-subset-sum test, and a search seeded by the known optimum for six elements. Mathematical Approach Write $\sigma(B)=\sum_{x\in B}x$. Once the candidate set is sorted increasingly, Problem 103 becomes a finite search with strong pruning: one rule collapses to a few linear inequalities, and the other can be checked exactly by enumerating subset masks. Reducing the size rule to prefix-versus-suffix inequalities Assume $a_1<a_2<\cdots<a_n$. Among all subsets of size $m+1$, the smallest possible sum is $a_1+\cdots+a_{m+1}$. Among all subsets of size $m$, the largest possible sum is $a_{n-m+1}+\cdots+a_n$....

Detailed mathematical approach

Problem Summary

For a set $A$ of positive integers, which the statement takes for granted (otherwise $\{0\}$ would beat its optimum $\{1\}$), let $S(A)$ be the sum of its elements. $A$ is a special sum set if any two non-empty disjoint subsets $B$ and $C$ satisfy two conditions: (i) $S(B)\ne S(C)$, and (ii) $S(B)\gt S(C)$ whenever $B$ has more elements than $C$. A special sum set of $n$ elements whose sum is as small as possible is an optimum special sum set; for $n=1,\dots,5$ the statement gives $\{1\}$, $\{1,2\}$, $\{2,3,4\}$, $\{3,5,6,7\}$ and $\{6,9,11,12,13\}$. It also describes a rule that seems to produce the next optimum set from an optimum set $\{a_1,\dots,a_n\}$: with its “middle” element $b$, form $\{b,a_1+b,\dots,a_n+b\}$. For $n=6$ the rule gives $\{11,17,20,22,23,24\}$ with sum $117$, but the optimum is $\{11,18,19,20,22,25\}$ with sum $115$ and the set string $111819202225$, the elements in increasing order written one after another. We must find the set string of the optimum special sum set for $n=7$. ^[1]

The whole solution in one sentence: the statement's rule, applied to the optimum for six elements with its larger middle element, gives a special sum set of seven elements, and a search through all increasing sequences of seven numbers with a smaller sum, which drops a partial sequence as soon as condition (ii) or the bound on the sum rules it out, either finds a better set or proves that none exists.

Mathematical Approach

We first check the smallest sets by hand, turn the two conditions into quick tests, prove that the rule always produces a special sum set, bound the optimum from below, and then search.

1. The smallest sets

One element has no pair of disjoint non-empty subsets, so $\{1\}$ is optimum. For $\{a,b\}$ with $a\lt b$ the only pair is $\{a\}$ and $\{b\}$, of equal size and with different sums, so every set of two different positive integers is special and $\{1,2\}$ is optimum. For $a\lt b\lt c$, condition (ii) with $B=\{a,b\}$ and $C=\{c\}$ demands $a+b\gt c$. This excludes $a=1$, because $c\ge b+1$. So the sum is at least $2+3+4=9$, and $\{2,3,4\}$ is optimum: even its smallest pair beats its largest element, $2+3\gt4$, and its subsets have the different sums $0,2,3,4,5,6,7,9$.

The two conditions are independent. $\{1,2,4\}$ satisfies (i), with the subset sums $0,1,\dots,7$, but not (ii), since $1+2\lt4$. $\{4,5,6,7\}$ satisfies (ii), because even its smallest pair beats its largest element, $4+5\gt7$ (Section 3 shows that such inequalities are all that (ii) needs), but not (i), since $4+7=5+6$.

2. Both conditions hold for all pairs of subsets

Let $B\ne C$ be any two subsets, disjoint or not. Removing their common part leaves the disjoint sets $B'=B\setminus C$ and $C'=C\setminus B$, and $S(B)-S(C)=S(B')-S(C')$; in $\{3,5,6,7\}$, for example, $\{3,5\}$ and $\{5,6\}$ give $8-11=3-6$. If both parts are non-empty, (i) makes the difference nonzero; if one is empty, the other is not, and the difference is nonzero because all elements are positive. So (i) says that all $2^n$ subsets have different sums. In the same way, if $B$ has more elements than $C$, then $B'$ has more than $C'$, and (ii), or positivity when $C'$ is empty, gives $S(B)\gt S(C)$. The subset sums are therefore sorted by size: in $\{3,5,6,7\}$ the empty set with $0$, the single elements, the pairs with the sums $8,\dots,13$, the triples with $14,15,16,18$ and the whole set with $21$ give sixteen different numbers in exactly this order. Finally, every subset of a special set is special, because its disjoint subsets are disjoint subsets of $A$.

3. The size condition in a few inequalities

Sort $a_1\lt\dots\lt a_n$. If $B$ and $C$ are disjoint, $C$ has $k\ge1$ elements and $B$ more, then $2k+1\le n$, $S(B)$ is at least the sum of the $k+1$ smallest elements and $S(C)$ at most the sum of the $k$ largest. So condition (ii) follows from the inequalities

$$a_1+\dots+a_{k+1}\gt a_{n-k+1}+\dots+a_n$$

for all $k\ge1$ with $2k+1\le n$, and they are also necessary, because the two groups in each of them are disjoint. For $n=7$ there are three:

$$\begin{aligned}a_1+a_2&\gt a_7,\\ a_1+a_2+a_3&\gt a_6+a_7,\\ a_1+a_2+a_3+a_4&\gt a_5+a_6+a_7.\end{aligned}$$

The optimum for $n=6$ passes its two inequalities narrowly: $11+18=29\gt25$ and $11+18+19=48\gt47=22+25$.

4. Subsets as binary numbers

A program stores a subset as a binary number, a mask, whose digit at position $i$, counted from the right and starting at $0$, is $1$ when $a_{i+1}$ belongs to the subset; the $2^n$ masks are the $2^n$ subsets. ^[2] For $\{3,5,6,7\}$, the mask $0101_2=5$ is $\{3,6\}$. The bitwise AND of two masks has a $1$ exactly where both have a $1$, so it is $0$ exactly for disjoint subsets: for $0101_2$ and $0110_2$, which is $\{5,6\}$, it is $0100_2$, the common element $6$, and for $0101_2$ and $1010_2$, which is $\{5,7\}$, it is $0$. All subset sums follow in one pass, because dropping the lowest digit $1$ gives a smaller mask whose sum is known: $1101_2$, which is $\{3,6,7\}$, has the sum of $1100_2$ plus $3$.

Every element goes into $B$, into $C$ or into neither, which gives $3^n$ ordered pairs $(B,C)$ of disjoint subsets. $B$ is empty in $2^n$ of them and $C$ in $2^n$; the pair of two empty sets is in both groups, so removing both groups removes it twice, and adding it back once leaves $3^n-2^{n+1}+1$ pairs with both parts non-empty. This is the inclusion–exclusion principle. ^[3] Swapping $B$ and $C$ matches these pairs two at a time, so there are $(3^n-2^{n+1}+1)/2$ unordered pairs: $1$ for $n=2$, the pair of Section 1, $25$ for $n=4$ and $966$ for $n=7$. Problem 106 notes ^[4] that once (ii) holds, only $1$ of the $25$ and $70$ of the $966$ need an equality test: (ii) settles subsets of different sizes, and subsets of equal size need no test when, in increasing order, each element of one is smaller than the corresponding element of the other. For $n=4$ only $\{a_1,a_4\}$ and $\{a_2,a_3\}$ remain, since $a_1\lt a_2$ but $a_4\gt a_3$: exactly where $\{4,5,6,7\}$ fails. The programs do not use this shortcut.

5. When the rule gives a special set

Let $A=\{a_1\lt\dots\lt a_n\}$ be special, let $m=\lfloor n/2\rfloor$ be $n/2$ rounded down ($m=2$ for $n=4$ and for $n=5$), and let $D(A)$ be the sum of the $m$ largest elements minus the sum of the $m$ smallest. It is the largest difference $S(Q)-S(P)$ of two disjoint subsets of equal size: for size $j$, $S(Q)$ is at most the sum of the $j$ largest elements and $S(P)$ at least the sum of the $j$ smallest, and going from $j$ to $j+1\le m$ adds the next largest element $a_{n-j}$ to the first sum and the next smallest $a_{j+1}$ to the second, which changes the difference by $a_{n-j}-a_{j+1}\ge0$. In $\{3,5,6,7\}$ the largest difference is $7-3=4$ for $j=1$; the step to $j=2$ adds $6$ to the first sum and $5$ to the second, so $D(A)=(6+7)-(3+5)=5$.

Claim. For a positive integer $b$, the set $A^+=\{b,a_1+b,\dots,a_n+b\}$ is special exactly when $b\gt D(A)$.

Proof. Every element of $A^+$ is $b$ plus an element of $A$ or, for $b$ itself, plus an extra element $0$. So a subset $X$ of $A^+$ with $|X|$ elements has the sum $b\,|X|+S(P)$, where $P$ is the set of elements of $A$ used in $X$. Let $X$ and $Y$ be non-empty and disjoint, with the disjoint sets $P$ and $Q$; swapping the names if necessary, we may assume $|X|\ge|Y|$.

If $|X|=|Y|$, the difference $S(X)-S(Y)$ is $S(P)-S(Q)$, nonzero by (i) for $A$ when $P$ and $Q$ are non-empty; otherwise one subset is $\{b\}$ and the other is a single larger element.
If $|X|\gt|Y|$ and $b$ is not in $X$, then $P$ has more elements than $Q$, so $S(P)\gt S(Q)$ by (ii) for $A$, or because $Q$ is empty, and $S(X)-S(Y)$, which is $b\,(|X|-|Y|)+S(P)-S(Q)$, is positive. The same holds if $b$ is in $X$ and $|X|\ge|Y|+2$.
If $b$ is in $X$ and $|X|=|Y|+1$, then $P$ and $Q$ have the same size, and $S(X)-S(Y)$ is $b-(S(Q)-S(P))\ge b-D(A)$.

So $A^+$ is special if $b\gt D(A)$. If $b\le D(A)$ and $n\ge2$, let $X$ be $b$ with the $m$ smallest shifted elements and $Y$ the $m$ largest shifted elements: $X$ is larger, but $S(X)-S(Y)=b-D(A)\le0$, so (ii) fails. This proves the claim.

Which $b$ satisfy $b\gt D(A)$? For odd $n=2m+1\ge3$, the inequality of Section 3 with $k=m$ turns into $a_{m+1}\gt D(A)$ when $a_1+\dots+a_m$ is subtracted from both sides. For even $n=2m\ge4$, the one with $k=m-1$ says $a_1+\dots+a_m\gt a_{m+2}+\dots+a_n$, and subtracting both sides from $a_{m+1}+\dots+a_n$ gives $D(A)\lt a_{m+1}$. For $n=1$, $D(A)=0\lt a_1$, and for $n=2$, $D(A)=a_2-a_1\lt a_2$. So $b=a_{m+1}$, the middle element or the larger of the two middle elements, is always allowed, and the rule produces special sum sets of every size; the new set has the sum $S(A)+(n+1)\,b$. Starting from $\{1\}$, with $D(A)=0,1,2,5,10$ and $b=1,2,3,6,11$, it gives $\{1,2\}$, $\{2,3,4\}$, $\{3,5,6,7\}$ and $\{6,9,11,12,13\}$, the optimum sets of the statement, and then the near-optimum set $\{11,17,20,22,23,24\}$ with the sum $51+6\cdot11=117$. Each time $b=D(A)+1$, the smallest allowed value. The smaller middle element can fail: for $\{3,5,6,7\}$ it is $5=D(A)$, and $\{5,8,10,11,12\}$ is not special, because $5+8+10=11+12$.

6. The rule is not always optimal

An exhaustive search through all special sets of six elements with sum at most $118$, done as in Section 8, finds only two: the optimum with sum $115$ and the rule's set with sum $117$. The optimum is not built by the rule from any special set: removing its smallest element $11$ and subtracting $11$ from the others leaves $\{7,8,9,11,14\}$, which breaks (ii) since $7+8+9\lt11+14$. So the rule only gives an upper bound, and for $n=7$ a search has to decide.

7. A lower bound from counting

The pigeonhole principle says that if more objects than boxes are put into boxes, some box gets two. ^[5] The $2^n$ different subset sums of Section 2 lie between $0$ and $S(A)$, so $S(A)\ge2^n-1$, only $127$ for $n=7$. A sharper count uses the $\binom nm$ subsets of $m=\lfloor n/2\rfloor$ elements, where the binomial coefficient counts the ways to choose $m$ elements out of $n$. ^[6] Their sums are different and lie between the sum of the $m$ smallest and the sum of the $m$ largest elements, so $D(A)\ge\binom nm-1$, and with $a_{m+1}\gt D(A)$ from Section 5,

$$a_{m+1}\ge\binom nm,\qquad m=\lfloor n/2\rfloor.$$

For $n=6$ this gives $a_4\ge20$, so $a_5+a_6\ge21+22=43$, the inequality $a_1+a_2+a_3\gt a_5+a_6$ of Section 3 forces $a_1+a_2+a_3\ge44$, and the sum is at least $44+20+43=107$. The optimum has $a_4=20$: its twenty triples have the sums $48,49,\dots,67$, each integer once. For $n=7$, $a_4\ge35$ gives $a_5+a_6+a_7\ge36+37+38=111$, the last inequality of Section 3 forces $a_1+a_2+a_3+a_4\ge112$, and the sum is at least $223$. The same reasoning gives the bounds $1,3,9,21,47,107,223$ for $n=1,\dots,7$, against the optimum sums $1,3,9,21,51,115$ for $n\le6$. Without condition (ii), sets with distinct subset sums are the subject of the Erdős distinct subset sums problem, where Dubroff, Fox and Xu proved with an isoperimetric inequality that the largest element is at least $\binom{n}{\lfloor n/2\rfloor}$. ^[7] Condition (ii) makes the bound elementary and moves it to the middle element.

8. Searching with bounds

Let $\sigma_0$ be the sum of the set that the rule builds from the optimum for $n-1$ elements. We need the special sets with a smaller sum, if any. Listing all candidates is wasteful: $2708390$ increasing sequences of six positive integers have a sum below $117$, and about $1.8\cdot10^9$ sequences of seven have a sum below the $\sigma_0$ for $n=7$. Two standard techniques cut this down.

Backtracking builds a candidate one element at a time, $a_1\lt a_2\lt\cdots$, and abandons a partial candidate as soon as it cannot be completed to a solution. ^[8] A partial candidate is itself a set, and every part of a special set is special (Section 2); so if the first $j$ elements already break an inequality of Section 3 for $j$ elements, no later elements can repair it. We call this check the prefix test. Once $11$ and $18$ are chosen, for example, every later element must be below $29$.

Branch and bound keeps the best solution found so far and discards every branch that cannot beat it. ^[9] If $j$ chosen elements have the sum $s$, $r=n-j$ are missing and the next is at least $v$, the cheapest completion $v,v+1,\dots,v+r-1$ has the sum $rv+r(r-1)/2$, and the branch is useless when $s+rv+r(r-1)/2$ reaches the best sum; we call this the bound test. It only gets harder to pass as $v$ grows, so the loop over the next element stops at the first $v$ that fails it. With the bound $117$ for $n=6$, the first element is at most $16$, because $17+18+\dots+22=117$.

Claim. The search ends with an optimum set. Suppose some special set has a sum below $\sigma_0$, and let $T$ be one with the smallest sum $\sigma^*$. The best sum always belongs to a special set, so it never drops below $\sigma^*$. No initial part of $T$ fails the prefix test, and while the best sum exceeds $\sigma^*$, none fails the bound test, since its cheapest completion costs at most $\sigma^*$. So the search either reaches and accepts $T$, or it has already found another special set with the sum $\sigma^*$. If no special set has a sum below $\sigma_0$, the starting set stays, and it is special by Section 5. The search does not show that the optimum is unique, as the statement assumes; the independent search under Complexity and Verification does.

9. Worked examples: three and six elements

For $n=3$ the search can be followed by hand. It starts from the rule's set $\{2,3,4\}$ with the bound $9$. The first element $1$ passes the bound test, since $1+2+3=6\lt9$. After $\{1,2\}$, the third elements $3$, $4$ and $5$ fail the prefix test, since $1+2$ is not larger than any of them, and $6$ stops the loop, since $1+2+6=9$. After $\{1,3\}$, $4$ fails, since $1+3=4$, and $5$ stops the loop, since $1+3+5=9$. Then the second element $4$ ends its loop, since $1+4+5=10$, and the first element $2$ ends the search, since $2+3+4=9$. So the function is called $4$ times, $4$ prefix tests fail, no complete set is reached, and $\{2,3,4\}$ is optimal, as in Section 1.

For $n=6$ the search starts from $\{11,17,20,22,23,24\}$ with the bound $117$ and calls the function $4728$ times. Of the $44713$ extensions it tries, $39986$ fail the prefix test; the $1157$ complete sets that reach the final test all pass its size test, which the last prefix test has already made, and the subset test rejects all but $\{11,18,19,20,22,25\}$, found at the $3201$st call. With the bound $115$ nothing smaller turns up, which proves optimality. Without the prefix test it would examine about $2.7$ million complete sets.

How the Code Works

The C++ program ^[10] first calls parse_arguments, which accepts only --skip-checkpoints; without that option, run_checkpoints makes sure that is_special_sum_set accepts $\{3,5,6,7\}$ and rejects $\{2,3,4,5\}$. is_special_sum_set checks with std::is_sorted that the values do not decrease (a repeated value would fail the subset test), then calls satisfies_size_order_rule, which uses prefix sums, the running totals $a_1+\dots+a_i$, to compare the $k+1$ smallest with the $k$ largest elements for $2k+1\le n$ (Section 3; the code calls this index m), and has_unique_disjoint_subset_sums. That function fills subset_sum for all $2^n$ masks as in Section 4: mask & (mask - 1) clears the lowest digit $1$, and __builtin_ctz, a GCC built-in that counts the trailing zero digits of a nonzero number, gives the position of that element. ^[11] It then runs through all pairs of masks a < b, skips those with a & b nonzero, and stops at the first equal sum: up to $8001$ pairs for seven elements, $966$ of them disjoint.

solve takes the starting set from near_optimum_seed_for_seven, which applies the rule to the optimum for six elements with the element at index size()/2, the larger middle element, as Section 5 requires; the program never tests this set, and Section 5 shows that it need not. Then search_best_set runs the search of Section 8: on entry it returns when current_sum plus the cheapest completion reaches best_sum; with seven elements it calls is_special_sum_set and, on success, updates best and best_sum; otherwise it tries $v=$next_value, $v+1$, and so on, leaves the loop at the first $v$ for which current_sum + v + min_rest reaches best_sum, and recurses only when partial_size_order_prune, a copy of the size test, accepts the partial set. For $n=7$ it is called $302860$ times, and $116735$ complete sets reach the final test. Finally solve joins the decimal digits of the best set.

The Python and Java programs start from the rule's set for seven elements, written into the code. Their size tests run over $k=1,\dots,n-1$; for $2k\ge n$ the two groups overlap, and without the common elements such an inequality is the one for $n-1-k$, or $a_1\gt0$, so these checks are harmless. Their subset tests compare each new mask with all earlier disjoint masks: Python keeps the earlier masks in a set and adds up the elements of each disjoint one again, and Java keeps the sum of each mask in a HashMap. Python's solve only tries sets near the starting one: the first element moved by at most $3$, and each other element the new first element plus the matching element of the optimum for six elements, moved by at most $3$. Such a neighbourhood search cannot exclude a better set far away; the exhaustive argument is the C++ search. Java's search lets each element run through the $30$ values after the previous one and stops only when the running sum exceeds bestSum, with no completion bound or prefix test. This window is an unproven restriction; it excludes $728$ of the C++ candidates, all with first element $31$, $32$ or $33$ and none special. No sum exceeds a few hundred, so the int variables of C++ and Java cannot overflow.

Complexity and Verification

In C++, testing one set costs a number of steps proportional to $n$ for the size condition with prefix sums, $2^n$ steps for the subset sums and up to $(2^n-1)(2^n-2)/2\approx4^n/2$ pairs of masks, although checking that the $2^n$ sums are all different, as in Section 2, would need only about $2^n$ steps with a table of the sums already seen. A search with $E$ extensions, each given one prefix test, and $L$ complete sets at the final test therefore takes at most about $nE+L\cdot4^n/2$ steps; $E$ and $L$ depend on the starting bound and on the pruning, and no simple formula gives them. For $n=7$ the C++ search has $E\approx4.8$ million and $L=116735$, with about $1.4\cdot10^8$ steps of pair loops. About $4.5$ million prefix tests fail; since the new element $v$ is the largest, it appears only on the right of the inequalities, so once a test fails it fails for every larger $v$, and leaving the loop at the first failure, which the program does not do, would cut the tests to about $0.47$ million with the same result. The run takes about $0.2$ seconds on a desktop computer; its memory is the recursion of depth $7$, a few vectors of at most eight numbers and the table of $128$ sums. Python and Java spend $n$ steps on each mask sum and keep at most $127$ masks per test; Python, which tries $7^7=823543$ shifted sets, takes about $3$ seconds, and Java, which reaches about $8.9\cdot10^8$ complete sequences, almost all rejected by the size test, about $7$. The number of subsets doubles with each new element, and $L$ grew a hundredfold from $1157$ for $n=6$, so the method suits small sizes such as $n=7$.

The C++ program checks two sets before the search, but $\{2,3,4,5\}$ already fails the size test, since $2+3=5$, so the subset test never rejects a set there; $\{4,5,6,7\}$ of Section 1, which passes the size test, would exercise it. Python and Java have no self-checks. Separate programs written for this article confirmed the reformulation of Sections 2 and 3 on $60000$ random sets of one to six numbers up to $80$ and on all $3472$ non-empty subsets of $\{1,\dots,14\}$ with at most five elements, the optimum sets of the statement as the only ones for $n\le6$, the claim of Section 5 for all $1102$ special sets of at most five numbers up to $18$ and every $b\le60$, the bounds of Section 7 for all special sets of $3$, $4$, $5$ and $6$ elements with sums up to $40$, $60$, $90$ and $140$, and, with a Python copy of search_best_set and instrumented copies of the programs, every count quoted above. An independent exhaustive search for $n=7$ through all $197204$ increasing sequences with $a_7\lt a_1+a_2$, initial parts passing the size test and sum at most $270$ finds exactly one optimum set, whose set string agrees with the output of all three programs.

Footnotes and References

The references supply background facts; the reformulations, the claim about the rule, the bounds and the correctness of the search are derived in this article.

Project Euler 103 — Special Subset Sums: Optimum. The statement defines special and optimum special sum sets, gives the optimum sets for n ≤ 6 and the set that the “middle element” rule builds for n = 6, and asks for the set string for n = 7.
Wikipedia — Power set. A set of n elements has 2ⁿ subsets; a subset can be written as a sequence of binary digits in which 1 means that the element belongs to it.
Wikipedia — Inclusion–exclusion principle. For two finite sets, |A ∪ B| = |A| + |B| − |A ∩ B|, because the elements of the intersection are counted twice in |A| + |B|.
Project Euler 106 — Special Subset Sums: Meta-testing. For increasing elements satisfying the second condition, only 1 of the 25 subset pairs for n = 4 and 70 of the 966 for n = 7 need an equality test.
Wikipedia — Pigeonhole principle. If n items are put into m containers with n > m, some container holds more than one item.
Wikipedia — Binomial coefficient. C(n, k) is the number of k-element subsets of an n-element set.
Q. Dubroff, J. Fox, M. W. Xu — A note on the Erdős distinct subset sums problem. The second of two short proofs of the best known asymptotic lower bound, via an isoperimetric inequality, shows that a set of n positive integers with distinct subset sums has a largest element of at least C(n, ⌊n/2⌋).
Wikipedia — Backtracking. Candidates are built incrementally, and a candidate is abandoned as soon as it cannot possibly be completed to a valid solution.
Wikipedia — Branch and bound. A branch is discarded if it cannot produce a better solution than the best one found so far; for minimisation, this is the case when its lower bound is greater than or equal to the current upper bound, the value of the best solution found. A tie can hide a second optimum, which is why the search of Section 8 finds one optimum but does not prove that it is unique.
C++ — Euler103.cpp. The immutable revision with search_best_set and run_checkpoints, the implementation record for this article.
GCC manual — Bit Operation Builtins. __builtin_ctz(x) returns the number of trailing 0-bits in x; for x = 0 the result is undefined, and the program never passes 0.

Problem 103 source code

C++

#include <algorithm>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>

namespace {

struct Options {
    bool run_checkpoints = 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;
        }

        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(const std::vector<int>& values) {
    if (!std::is_sorted(values.begin(), values.end())) {
        return false;
    }
    if (!satisfies_size_order_rule(values)) {
        return false;
    }
    if (!has_unique_disjoint_subset_sums(values)) {
        return false;
    }
    return true;
}

bool partial_size_order_prune(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;
}

std::vector<int> near_optimum_seed_for_seven() {
    const std::vector<int> previous_optimum = {11, 18, 19, 20, 22, 25};
    const int middle = previous_optimum[previous_optimum.size() / 2];

    std::vector<int> seed;
    seed.push_back(middle);
    for (int v : previous_optimum) {
        seed.push_back(middle + v);
    }
    return seed;
}

void search_best_set(const int target_size,
                     int index,
                     int next_value,
                     int current_sum,
                     std::vector<int>& current,
                     std::vector<int>& best,
                     int& best_sum) {
    const int remaining = target_size - index;
    const int min_possible_tail = remaining * next_value + (remaining * (remaining - 1)) / 2;
    if (current_sum + min_possible_tail >= best_sum) {
        return;
    }

    if (index == target_size) {
        if (is_special_sum_set(current)) {
            best_sum = current_sum;
            best = current;
        }
        return;
    }

    for (int v = next_value;; ++v) {
        const int rest = target_size - index - 1;
        const int min_rest = rest * (v + 1) + (rest * (rest - 1)) / 2;
        if (current_sum + v + min_rest >= best_sum) {
            break;
        }

        current.push_back(v);
        if (partial_size_order_prune(current)) {
            search_best_set(target_size, index + 1, v + 1, current_sum + v, current, best, best_sum);
        }
        current.pop_back();
    }
}

std::string solve() {
    std::vector<int> best = near_optimum_seed_for_seven();
    int best_sum = std::accumulate(best.begin(), best.end(), 0);

    std::vector<int> current;
    search_best_set(7, 0, 1, 0, current, best, best_sum);

    std::string concat;
    for (int v : best) {
        concat += std::to_string(v);
    }
    return concat;
}

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

    std::cout << solve() << '\n';
    return 0;
}

Python

# Problem 103: Special subset sums: optimum
# The answer is known to be {20, 31, 38, 39, 40, 42, 45} via exhaustive search.
# We use the near-optimum seeding approach and a tighter search.

from itertools import combinations

def is_special_sum_set(s):
    s = sorted(s)
    n = len(s)
    # Rule 3: |B| > |C| => S(B) > S(C)
    for k in range(1, n):
        if sum(s[:k+1]) <= sum(s[n-k:]):
            return False
    # Rule 2: all disjoint subset pairs have different sums
    seen = set()
    for mask in range(1, 1 << n):
        total = sum(s[i] for i in range(n) if mask & (1 << i))
        for prev_mask in list(seen):
            if prev_mask & mask == 0:
                prev_total = sum(s[i] for i in range(n) if prev_mask & (1 << i))
                if prev_total == total:
                    return False
        seen.add(mask)
    return True

def solve():
    # The near-optimum seed for n=7 built from n=6 optimum {11,18,19,20,22,25}
    # b = middle(n=6) = 20, answer candidate = {b, b+a1, ...}
    seed = [20, 31, 38, 39, 40, 42, 45]
    best_sum = sum(seed)
    best = seed[:]
    
    # Search around seed with tight bounds
    for delta in range(-3, 4):
        base = 20 + delta
        for d1 in range(-3, 4):
            for d2 in range(-3, 4):
                for d3 in range(-3, 4):
                    for d4 in range(-3, 4):
                        for d5 in range(-3, 4):
                            for d6 in range(-3, 4):
                                s = sorted([base, base+11+d1, base+18+d2, base+19+d3, base+20+d4, base+22+d5, base+25+d6])
                                if len(set(s)) != 7 or s[0] < 1:
                                    continue
                                cs = sum(s)
                                if cs >= best_sum:
                                    continue
                                if is_special_sum_set(s):
                                    best = s[:]
                                    best_sum = cs
    
    print(''.join(str(x) for x in best))

solve()

Java

import java.util.*;

public class Euler103 {
    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;
    }

    static int[] best;
    static int bestSum;

    static void search(int idx, int[] current, int minVal, int curSum) {
        if (idx == 7) {
            if (curSum < bestSum && isSpecial(current.clone())) {
                best = current.clone();
                bestSum = curSum;
            }
            return;
        }
        for (int v = minVal; v < minVal + 30; v++) {
            if (curSum + v > bestSum)
                break;
            current[idx] = v;
            search(idx + 1, current, v + 1, curSum + v);
        }
    }

    public static void main(String[] args) {
        best = new int[] { 20, 31, 38, 39, 40, 42, 45 };
        bestSum = Arrays.stream(best).sum();
        search(0, new int[7], 1, 0);
        StringBuilder sb = new StringBuilder();
        for (int v : best)
            sb.append(v);
        System.out.println(sb);
    }
}