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.
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.
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\). Therefore the condition
$$|B|>|C| \Longrightarrow \sigma(B)>\sigma(C)$$
is guaranteed once we verify
$$a_1+\cdots+a_{m+1} > a_{n-m+1}+\cdots+a_n \qquad \left(m=1,2,\dots,\left\lfloor\frac{n-1}{2}\right\rfloor\right).$$
For \(n=7\), this becomes only three inequalities:
$$a_1+a_2>a_7,\qquad a_1+a_2+a_3>a_6+a_7,\qquad a_1+a_2+a_3+a_4>a_5+a_6+a_7.$$
This lemma is the main fast filter in every implementation.
The standard near-optimum construction starts from the optimum special sum set of size 6, namely \(\{11,18,19,20,22,25\}\). Let the middle element be \(b=20\). The usual template for the next size is
$$\{b\}\cup\{b+x:x\in\{11,18,19,20,22,25\}\}=\{20,31,38,39,40,42,45\}.$$
This already has total sum \(255\), so it immediately provides an upper bound: any better solution would need sum strictly less than 255. The search procedures are organized around trying to beat that bound.
For \(A=\{20,31,38,39,40,42,45\}\), the three required comparisons are
$$20+31=51>45,\qquad 20+31+38=89>42+45=87,\qquad 20+31+38+39=128>40+42+45=127.$$
So the larger-subset-larger-sum rule already holds. This is important because it means the candidate survives the cheapest structural test before any expensive subset enumeration is performed.
The second rule is subtler. We do not need all subset sums to be distinct; we only need equality to be impossible for two disjoint non-empty subsets. For \(n=7\), there are \(2^7-1=127\) non-empty subsets, so the implementations enumerate masks \(M\) and compute \(\sigma(M)\). A candidate fails as soon as two masks satisfy
$$M\cap N=\varnothing,\qquad \sigma(M)=\sigma(N).$$
In the fastest implementation, subset sums are filled incrementally by removing the least significant chosen element, which gives the recurrence
$$\sigma(M)=\sigma\!\bigl(M\setminus\{\ell\}\bigr)+a_\ell.$$
At this problem size, exact enumeration is completely practical.
Suppose an increasing prefix \(a_1<\cdots<a_k\) has already been chosen, its current sum is \(S_{\mathrm{cur}}\), and the next value must be at least \(v\). If \(r=7-k\) elements remain, then the smallest possible completion is \(v,v+1,\dots,v+r-1\), so every extension has total at least
$$S_{\mathrm{cur}}+v+(v+1)+\cdots+(v+r-1)=S_{\mathrm{cur}}+rv+\frac{r(r-1)}{2}.$$
If this lower bound is already at least the best known sum, the entire branch can be discarded. The exhaustive implementations also reuse the prefix-versus-suffix inequalities on partial prefixes: once a partial set violates one of those inequalities, adding larger future values cannot repair it.
Starting from the upper bound 255 supplied by the template, the exhaustive search enumerates all strictly increasing seven-element candidates that could possibly beat it, pruning branches that are already hopeless. Every full candidate is then checked against both special-sum conditions. Since no valid set with smaller total sum exists, the template itself is optimal, giving \(\{20,31,38,39,40,42,45\}\) and the string \(20313839404245\).
The C++, Python, and Java implementations all treat candidates as increasing sequences and all use the same two mathematical validators: the prefix-suffix inequalities for the size rule and a disjoint-subset-sum check for the uniqueness rule.
The implementations differ mainly in the search layer. The C++ version performs a full branch-and-bound search with a strong arithmetic lower bound for the unfinished tail. The Java version also searches recursively from the template upper bound, but with a simpler next-value window. The Python version explores a tight neighborhood around the standard seven-element template built from the six-element optimum. In all three languages, the same special-sum conditions determine whether a candidate survives.
When a candidate reaches length 7, the implementation verifies that it is sorted, applies the size-rule filter, enumerates the non-empty subset masks, and rejects the candidate immediately if a disjoint equal-sum pair appears. Any valid set with a smaller total replaces the current best answer.
For a fixed set of size \(n\), the size-rule test costs \(O(n)\). The subset stage needs \(O(2^n)\) masks, and the straightforward disjoint-pair comparison used here is exponential as well; stated conservatively, the full validator is at most \(O(4^n)\), which is still tiny for \(n=7\).
The outer search is also exponential in principle, because it ranges over candidate sets. The reason the problem is still easy in practice is that the upper bound \(255\) is already extremely tight, and the lower bound \(S_{\mathrm{cur}}+rv+\frac{r(r-1)}{2}\) removes large parts of the tree before the expensive subset test is even reached. For this fixed seven-element case, the optimum is certified quickly.
Gesucht ist eine streng wachsende Menge \(A=\{a_1,a_2,\dots,a_7\}\) positiver ganzer Zahlen mit minimaler Gesamtsumme, so dass zwei Bedingungen gelten. Erstens dürfen keine zwei nichtleeren disjunkten Teilmengen dieselbe Summe besitzen. Zweitens muss bei zwei disjunkten Teilmengen die größere Mächtigkeit immer auch die größere Summe erzwingen. Die optimale Menge ist \(\{20,31,38,39,40,42,45\}\), also lautet der aus den Elementen gebildete String \(20313839404245\).
Die vorhandenen Implementierungen benutzen keine geschlossene Formel. Sie kombinieren stattdessen ein starkes Strukturlemma für die Größenbedingung, eine exakte Prüfung auf gleiche Summen disjunkter Teilmengen und eine Suche, die mit der bekannten optimalen Sechsermenge startet.
Sei \(\sigma(B)=\sum_{x\in B}x\). Sobald die Kandidatenmenge aufsteigend sortiert ist, zerfällt Problem 103 in eine endliche Suche mit starker Beschneidung: Eine Bedingung reduziert sich auf wenige lineare Ungleichungen, die andere auf eine vollständige Bitmasken-Prüfung aller relevanten Teilmengen.
Nehmen wir \(a_1<a_2<\cdots<a_n\) an. Unter allen Teilmengen der Größe \(m+1\) ist die kleinste mögliche Summe gleich \(a_1+\cdots+a_{m+1}\). Unter allen Teilmengen der Größe \(m\) ist die größte mögliche Summe gleich \(a_{n-m+1}+\cdots+a_n\). Deshalb ist
$$|B|>|C| \Longrightarrow \sigma(B)>\sigma(C)$$
bereits gesichert, wenn nur
$$a_1+\cdots+a_{m+1} > a_{n-m+1}+\cdots+a_n \qquad \left(m=1,2,\dots,\left\lfloor\frac{n-1}{2}\right\rfloor\right)$$
gilt. Für \(n=7\) bleiben genau drei Tests:
$$a_1+a_2>a_7,\qquad a_1+a_2+a_3>a_6+a_7,\qquad a_1+a_2+a_3+a_4>a_5+a_6+a_7.$$
Dieses Lemma ist in allen drei Sprachen der wichtigste schnelle Vorfilter.
Die übliche nahezu optimale Konstruktion beginnt mit der optimalen Spezial-Summenmenge der Größe 6, nämlich \(\{11,18,19,20,22,25\}\). Ihr mittleres Element ist \(b=20\). Daraus entsteht für die nächste Größe die Standardschablone
$$\{b\}\cup\{b+x:x\in\{11,18,19,20,22,25\}\}=\{20,31,38,39,40,42,45\}.$$
Diese Menge hat bereits die Gesamtsumme \(255\). Damit erhalten wir sofort eine scharfe obere Schranke: Jede bessere Lösung müsste eine kleinere Summe als 255 besitzen. Genau auf diesen Versuch richtet sich die Suche.
Für \(A=\{20,31,38,39,40,42,45\}\) lauten die drei nötigen Vergleiche
$$20+31=51>45,\qquad 20+31+38=89>42+45=87,\qquad 20+31+38+39=128>40+42+45=127.$$
Damit ist die Regel „größere Teilmenge hat größere Summe“ bereits erfüllt. Gerade deshalb ist diese Prüfung ein so wirksamer früher Filter, bevor die aufwendigere Teilmengenprüfung beginnt.
Die zweite Bedingung ist kombinatorisch. Nicht alle Teilmengensummen müssen verschieden sein; verboten sind nur Gleichheiten zwischen zwei disjunkten nichtleeren Teilmengen. Für \(n=7\) gibt es \(2^7-1=127\) nichtleere Teilmengen, also enumerieren die Implementierungen Bitmasken \(M\) und berechnen \(\sigma(M)\). Ein Kandidat scheitert sofort, sobald
$$M\cap N=\varnothing,\qquad \sigma(M)=\sigma(N)$$
für zwei Masken \(M,N\) gilt. In der schnellsten Variante werden die Teilmengensummen inkrementell über die kleinste gesetzte Position aufgebaut:
$$\sigma(M)=\sigma\!\bigl(M\setminus\{\ell\}\bigr)+a_\ell.$$
Bei nur sieben Elementen ist diese exakte Prüfung problemlos bezahlbar.
Angenommen, ein wachsendes Präfix \(a_1<\cdots<a_k\) ist bereits gewählt, seine aktuelle Summe sei \(S_{\mathrm{cur}}\), und der nächste Wert muss mindestens \(v\) sein. Wenn noch \(r=7-k\) Elemente fehlen, dann ist die kleinste mögliche Ergänzung \(v,v+1,\dots,v+r-1\). Also besitzt jede Fortsetzung mindestens die Summe
$$S_{\mathrm{cur}}+v+(v+1)+\cdots+(v+r-1)=S_{\mathrm{cur}}+rv+\frac{r(r-1)}{2}.$$
Ist diese Untergrenze bereits nicht besser als die aktuell beste Summe, kann der ganze Suchzweig abgeschnitten werden. Die vollständigen Suchvarianten prüfen dieselben Präfix-Suffix-Ungleichungen sogar schon auf Teilpräfixen: Eine dort auftretende Verletzung kann durch spätere, noch größere Werte nicht mehr geheilt werden.
Ausgehend von der oberen Schranke 255 durchläuft die vollständige Suche alle streng wachsenden Siebenermengen, die theoretisch besser sein könnten, und verwirft aussichtslose Zweige frühzeitig. Jede vollständige Kandidatenmenge wird danach gegen beide Spezial-Summen-Bedingungen getestet. Weil keine gültige Menge mit kleinerer Gesamtsumme existiert, ist die Schablone selbst optimal. Damit erhält man \(\{20,31,38,39,40,42,45\}\) und den String \(20313839404245\).
Die C++-, Python- und Java-Implementierungen behandeln Kandidaten durchgängig als streng wachsende Folgen und verwenden dieselben beiden mathematischen Prüfer: die Präfix-Suffix-Ungleichungen für die Größenbedingung und die Prüfung auf gleiche Summen disjunkter Teilmengen für die Eindeutigkeitsbedingung.
Die Unterschiede liegen vor allem in der Suche. Die C++-Version führt eine vollständige Branch-and-Bound-Suche mit einer starken arithmetischen Untergrenze für den noch fehlenden Rest aus. Die Java-Version durchsucht ebenfalls rekursiv den Raum unter derselben oberen Schranke, aber mit einem gröberen Fenster für den nächsten Wert. Die Python-Version untersucht eine enge Nachbarschaft der Standardschablone, die aus der optimalen Sechsermenge entsteht. In allen drei Fällen entscheiden dieselben Spezial-Summen-Regeln über Gültigkeit oder Verwerfung.
Sobald ein Kandidat Länge 7 erreicht, überprüft die Implementierung die Sortierung, wendet den schnellen Größenfilter an, enumeriert die nichtleeren Teilmengenmasken und bricht sofort ab, wenn ein disjunktes Gleichsummenpaar auftaucht. Eine gültige Menge mit kleinerer Gesamtsumme ersetzt die bisher beste Lösung.
Für eine feste Menge der Größe \(n\) kostet der Größenfilter \(O(n)\). Die Teilmengenphase benötigt \(O(2^n)\) Masken, und der hier verwendete direkte Vergleich disjunkter Paare ist ebenfalls exponentiell; konservativ formuliert liegt der vollständige Prüfer höchstens bei \(O(4^n)\). Für \(n=7\) ist das jedoch immer noch sehr klein.
Auch die äußere Suche ist prinzipiell exponentiell, weil Mengenkandidaten durchlaufen werden. Praktisch bleibt die Rechnung schnell, weil die obere Schranke \(255\) bereits extrem eng ist und die Untergrenze \(S_{\mathrm{cur}}+rv+\frac{r(r-1)}{2}\) große Teile des Suchbaums entfernt, bevor die teure Teilmengenprüfung überhaupt beginnt. Für den festen Fall \(n=7\) ist die Optimalität daher rasch zertifiziert.
Aranan şey, toplamı mümkün olduğunca küçük olan ve iki koşulu sağlayan artan bir \(A=\{a_1,a_2,\dots,a_7\}\) pozitif tam sayı kümesidir. Birinci koşul, boş olmayan ayrık iki alt kümenin aynı toplamı verememesidir. İkinci koşul ise, ayrık iki alt kümeden eleman sayısı daha büyük olanın toplamının da daha büyük olmasını zorunlu kılar. En iyi küme \(\{20,31,38,39,40,42,45\}\) olduğundan istenen birleşik sayı dizisi \(20313839404245\) olur.
Verilen uygulamalar kapalı bir formül kullanmaz. Bunun yerine, eleman sayısı koşulunu birkaç eşitsizliğe indiren bir lemma, ayrık alt kümeler için açık bir toplam kontrolü ve altı elemanlı en iyi kümeden türetilen bir başlangıç üst sınırı kullanırlar.
\(\sigma(B)=\sum_{x\in B}x\) yazalım. Aday küme küçükten büyüğe sıralandığında Problem 103 sonlu ve güçlü biçimde budanabilen bir aramaya dönüşür: koşullardan biri birkaç doğrusal karşılaştırmayla, diğeri ise bitmask üzerinden tam bir taramayla denetlenebilir.
\(a_1<a_2<\cdots<a_n\) olsun. \(m+1\) elemanlı tüm alt kümeler arasında en küçük toplam \(a_1+\cdots+a_{m+1}\), \(m\) elemanlı tüm alt kümeler arasında en büyük toplam ise \(a_{n-m+1}+\cdots+a_n\) olur. Bu yüzden
$$|B|>|C| \Longrightarrow \sigma(B)>\sigma(C)$$
koşulu şu eşitsizlikler sağlanıyorsa otomatik olarak doğrudur:
$$a_1+\cdots+a_{m+1} > a_{n-m+1}+\cdots+a_n \qquad \left(m=1,2,\dots,\left\lfloor\frac{n-1}{2}\right\rfloor\right).$$
\(n=7\) için bu durum yalnızca üç teste iner:
$$a_1+a_2>a_7,\qquad a_1+a_2+a_3>a_6+a_7,\qquad a_1+a_2+a_3+a_4>a_5+a_6+a_7.$$
Bütün uygulamalardaki en hızlı ön filtre budur.
Standart yakın-optimal yapı, 6 elemanlı en iyi özel toplam kümesi olan \(\{11,18,19,20,22,25\}\) ile başlar. Orta eleman \(b=20\) alınır. Sonraki boyut için klasik şablon
$$\{b\}\cup\{b+x:x\in\{11,18,19,20,22,25\}\}=\{20,31,38,39,40,42,45\}$$
şeklindedir. Bu kümenin toplamı zaten \(255\) olduğundan, arama için çok güçlü bir üst sınır elde ederiz: gerçek optimum varsa ancak 255'ten daha küçük bir toplamla gelebilir.
\(A=\{20,31,38,39,40,42,45\}\) için gerekli üç karşılaştırma
$$20+31=51>45,\qquad 20+31+38=89>42+45=87,\qquad 20+31+38+39=128>40+42+45=127$$
olur. Böylece büyük alt kümenin daha büyük toplam vermesi koşulu daha derin aramaya geçmeden sağlanmış olur. Arama sırasında bu ön testin bu kadar etkili olmasının nedeni tam olarak budur.
İkinci koşul daha ince bir koşuldur. Bütün alt küme toplamlarının birbirinden farklı olması gerekmez; yasak olan şey, boş olmayan iki ayrık alt kümenin aynı toplamı vermesidir. \(n=7\) için \(2^7-1=127\) boş olmayan alt küme vardır. Uygulamalar maske \(M\) için \(\sigma(M)\) değerini hesaplar ve şu durum oluşur oluşmaz adayı reddeder:
$$M\cap N=\varnothing,\qquad \sigma(M)=\sigma(N).$$
En hızlı sürümde alt küme toplamları, maskeden en düşük anlamlı seçili elemanı çıkarma fikriyle artımlı olarak doldurulur:
$$\sigma(M)=\sigma\!\bigl(M\setminus\{\ell\}\bigr)+a_\ell.$$
Yedi eleman için bu tam tarama tamamen uygulanabilirdir.
Diyelim ki artan bir \(a_1<\cdots<a_k\) ön eki seçildi, mevcut toplam \(S_{\mathrm{cur}}\) ve bir sonraki değer en az \(v\) olmalı. Geriye \(r=7-k\) eleman kalıyorsa, mümkün olan en küçük tamamlama \(v,v+1,\dots,v+r-1\) olur. O halde her uzantının toplamı en az
$$S_{\mathrm{cur}}+v+(v+1)+\cdots+(v+r-1)=S_{\mathrm{cur}}+rv+\frac{r(r-1)}{2}$$
kadardır. Bu alt sınır mevcut en iyi toplamı artık geçemiyorsa, ilgili dal tamamen budanır. Tam arama yapan sürümler ayrıca önek-sonek eşitsizliklerini kısmi ön ekler üzerinde de uygular; çünkü burada oluşan bir ihlal, daha sonra eklenecek daha büyük sayılarla düzeltilemez.
Arama 255 üst sınırından başlar ve bundan daha iyi olabilecek tüm artan yedi elemanlı adayları, umutsuz dalları erken keserek tarar. Uzunluğu 7 olan her aday daha sonra iki özel toplam koşuluna karşı eksiksiz biçimde doğrulanır. Daha küçük toplamlı geçerli bir küme bulunmadığı için şablonun kendisi optimumdur. Böylece sonuç \(\{20,31,38,39,40,42,45\}\) ve istenen çıktı \(20313839404245\) olur.
C++, Python ve Java uygulamaları adayları artan diziler olarak ele alır ve aynı iki matematiksel denetleyiciyi kullanır: eleman sayısı kuralı için önek-sonek eşitsizlikleri ve benzersizlik kuralı için ayrık alt küme toplamı testi.
Asıl fark arama katmanındadır. C++ sürümü, tamamlanmamış kuyruğun en küçük olası toplamını hesaplayan güçlü bir branch-and-bound araması yapar. Java sürümü de aynı üst sınır altında özyinelemeli arama yapar, ancak bir sonraki değer için daha kaba bir pencere kullanır. Python sürümü ise altı elemanlı optimumdan türetilen standart yedi elemanlı şablonun dar bir komşuluğunu dolaşır. Üç dilde de bir adayın yaşayıp yaşamayacağına karar veren şey aynı özel toplam koşullarıdır.
Bir aday uzunluk 7'ye ulaştığında uygulama önce sıralılığı doğrular, hızlı eleman sayısı filtresini uygular, sonra boş olmayan alt küme maskelerini enumerate eder ve ayrık bir eş-toplam çifti görür görmez adayı eler. Toplamı daha küçük olan her geçerli küme mevcut en iyi cevabın yerini alır.
Sabit bir \(n\) elemanlı küme için eleman sayısı testi \(O(n)\) zaman alır. Alt küme aşaması \(O(2^n)\) maske gerektirir; burada kullanılan doğrudan ayrık çift karşılaştırması da üstel yapıdadır. Temkinli bir üst sınır olarak tüm doğrulayıcıyı \(O(4^n)\) içinde düşünebiliriz; fakat \(n=7\) olduğundan bu mutlak olarak çok küçüktür.
Dış arama da ilke olarak üstel davranır, çünkü aday kümeler üzerinde dolaşır. Buna rağmen pratikte hızlıdır; çünkü \(255\) üst sınırı çok sıkıdır ve \(S_{\mathrm{cur}}+rv+\frac{r(r-1)}{2}\) alt sınırı, pahalı alt küme denetimine gelmeden arama ağacının büyük bölümünü keser. Sabit yedi elemanlı bu problem için optimum bu yüzden hızlıca doğrulanır.
Buscamos un conjunto creciente de siete enteros positivos \(A=\{a_1,a_2,\dots,a_7\}\) con la menor suma total posible, sujeto a dos reglas. La primera dice que no puede haber dos subconjuntos no vacíos y disjuntos con la misma suma. La segunda exige que, si dos subconjuntos disjuntos tienen distinto tamaño, entonces el de mayor cardinalidad también debe tener la suma mayor. El conjunto óptimo es \(\{20,31,38,39,40,42,45\}\), por lo que la cadena pedida es \(20313839404245\).
Las implementaciones dadas no usan una fórmula cerrada. Combinan una reducción estructural muy fuerte para la regla de tamaños, una verificación explícita de sumas en subconjuntos disjuntos y una búsqueda inicializada con el óptimo conocido para 6 elementos.
Escribamos \(\sigma(B)=\sum_{x\in B}x\). Una vez que el conjunto candidato está ordenado de menor a mayor, el problema se convierte en una búsqueda finita con mucha poda: una condición se reduce a unas pocas desigualdades lineales y la otra puede comprobarse exactamente recorriendo máscaras de subconjuntos.
Supongamos \(a_1<a_2<\cdots<a_n\). Entre todos los subconjuntos de tamaño \(m+1\), la suma mínima posible es \(a_1+\cdots+a_{m+1}\). Entre todos los subconjuntos de tamaño \(m\), la suma máxima posible es \(a_{n-m+1}+\cdots+a_n\). Por tanto, la condición
$$|B|>|C| \Longrightarrow \sigma(B)>\sigma(C)$$
queda garantizada si verificamos solamente
$$a_1+\cdots+a_{m+1} > a_{n-m+1}+\cdots+a_n \qquad \left(m=1,2,\dots,\left\lfloor\frac{n-1}{2}\right\rfloor\right).$$
Para \(n=7\), esto se reduce a tres comparaciones:
$$a_1+a_2>a_7,\qquad a_1+a_2+a_3>a_6+a_7,\qquad a_1+a_2+a_3+a_4>a_5+a_6+a_7.$$
Este es el filtro rápido principal en todas las versiones.
La construcción casi óptima estándar parte del conjunto especial óptimo de tamaño 6, \(\{11,18,19,20,22,25\}\). Su elemento central es \(b=20\). La plantilla habitual para el siguiente tamaño es
$$\{b\}\cup\{b+x:x\in\{11,18,19,20,22,25\}\}=\{20,31,38,39,40,42,45\}.$$
Su suma total ya es \(255\), de modo que proporciona una cota superior excelente: cualquier solución mejor tendría que sumar estrictamente menos que 255. Toda la búsqueda se organiza alrededor de intentar mejorar esa cota.
Para \(A=\{20,31,38,39,40,42,45\}\), las tres comparaciones necesarias son
$$20+31=51>45,\qquad 20+31+38=89>42+45=87,\qquad 20+31+38+39=128>40+42+45=127.$$
Así, la regla de que un subconjunto más grande tenga suma mayor ya queda satisfecha. Por eso esta comprobación es tan valiosa como filtro previo antes de entrar en la enumeración más costosa de subconjuntos.
La segunda regla es más delicada. No hace falta que todas las sumas de subconjuntos sean distintas; solo se prohíbe la igualdad entre dos subconjuntos no vacíos y disjuntos. Para \(n=7\) hay \(2^7-1=127\) subconjuntos no vacíos, así que las implementaciones recorren máscaras \(M\) y calculan \(\sigma(M)\). Un candidato falla tan pronto como aparecen dos máscaras con
$$M\cap N=\varnothing,\qquad \sigma(M)=\sigma(N).$$
En la variante más rápida, las sumas de subconjuntos se rellenan de forma incremental quitando el elemento seleccionado de menor bit significativo, lo que da la recurrencia
$$\sigma(M)=\sigma\!\bigl(M\setminus\{\ell\}\bigr)+a_\ell.$$
Con solo siete elementos, esa verificación exhaustiva es perfectamente asequible.
Supongamos que ya se eligió un prefijo creciente \(a_1<\cdots<a_k\), cuya suma actual es \(S_{\mathrm{cur}}\), y que el siguiente valor permitido es al menos \(v\). Si faltan \(r=7-k\) elementos, la terminación más pequeña posible es \(v,v+1,\dots,v+r-1\). Por tanto, cualquier extensión tendrá suma total al menos
$$S_{\mathrm{cur}}+v+(v+1)+\cdots+(v+r-1)=S_{\mathrm{cur}}+rv+\frac{r(r-1)}{2}.$$
Si esa cota inferior ya no puede mejorar la mejor suma conocida, toda la rama se poda. Las implementaciones exhaustivas además reutilizan las desigualdades prefijo-sufijo en prefijos parciales: si ya fallan allí, añadir valores futuros todavía mayores no puede reparar el daño.
Partiendo de la cota superior 255 dada por la plantilla, la búsqueda exhaustiva enumera todos los candidatos crecientes de siete elementos que podrían ser mejores y corta pronto las ramas sin esperanza. Cada candidato completo se somete después a las dos condiciones de conjunto especial. Como no aparece ningún conjunto válido con suma menor, la propia plantilla es óptima. De ahí salen \(\{20,31,38,39,40,42,45\}\) y la cadena \(20313839404245\).
Las implementaciones en C++, Python y Java tratan los candidatos como secuencias crecientes y aplican las mismas dos pruebas matemáticas: las desigualdades prefijo-sufijo para la regla de tamaños y la comprobación de sumas en subconjuntos disjuntos para la regla de unicidad.
La principal diferencia está en la capa de búsqueda. La versión en C++ realiza una búsqueda branch-and-bound completa con una cota inferior aritmética fuerte para la cola que falta construir. La versión en Java también busca de forma recursiva bajo la misma cota superior, aunque con una ventana más simple para el siguiente valor. La versión en Python recorre un vecindario estrecho alrededor de la plantilla estándar de siete elementos construida a partir del óptimo de seis. En los tres casos, las mismas reglas de conjuntos especiales deciden si un candidato se acepta o se descarta.
Cuando un candidato alcanza longitud 7, la implementación verifica que esté ordenado, aplica el filtro rápido de tamaños, enumera las máscaras de todos los subconjuntos no vacíos y rechaza inmediatamente el candidato si aparece un par disjunto con la misma suma. Todo conjunto válido con suma menor sustituye a la mejor respuesta actual.
Para un conjunto fijo de tamaño \(n\), la prueba de tamaños cuesta \(O(n)\). La fase de subconjuntos necesita \(O(2^n)\) máscaras y la comparación directa de pares disjuntos usada aquí sigue siendo exponencial; como cota conservadora, el validador completo queda a lo sumo en \(O(4^n)\). Para \(n=7\), eso sigue siendo muy pequeño en términos absolutos.
La búsqueda externa también es exponencial en principio, porque recorre conjuntos candidatos. En la práctica resulta rápida porque la cota superior \(255\) ya es muy ajustada y la cota inferior \(S_{\mathrm{cur}}+rv+\frac{r(r-1)}{2}\) elimina grandes porciones del árbol antes de llegar a la costosa verificación de subconjuntos. En este caso fijo de siete elementos, la optimalidad se certifica sin dificultad.
我们要寻找一个严格递增的七元正整数集合 \(A=\{a_1,a_2,\dots,a_7\}\)，使它的元素总和尽可能小，并且满足两条特殊和集合条件。第一条是：任意两个非空且互不相交的子集不能有相同的元素和。第二条是：如果两个互不相交子集的元素个数不同，那么元素更多的那个子集，其元素和也必须更大。这个问题的最优集合是 \(\{20,31,38,39,40,42,45\}\)，因此最终需要输出的拼接字符串是 \(20313839404245\)。
给出的实现并不是依靠某个封闭公式直接写出答案，而是把问题拆成三个部分：先用一个很强的结构性引理快速过滤掉不可能的候选集合，再对剩下的候选集合做精确的互斥子集求和检查，最后利用六元最优集合构造出的七元模板作为搜索上界，从而完成最优性的证明。
记 \(\sigma(B)=\sum_{x\in B}x\)。当候选集合按从小到大排序之后，Problem 103 的两个条件就不再是抽象定义，而是变成了“少量线性不等式 + 有限个子集掩码检查”的组合。正因为 \(n=7\) 很小，这种完整搜索才是现实可行的。
设 \(a_1<a_2<\cdots<a_n\)。在所有含 \(m+1\) 个元素的子集中，和最小的一定是最小的那 \(m+1\) 个数，也就是 \(a_1+\cdots+a_{m+1}\)。在所有含 \(m\) 个元素的子集中，和最大的一定是最大的那 \(m\) 个数，也就是 \(a_{n-m+1}+\cdots+a_n\)。因此，只要验证
$$|B|>|C| \Longrightarrow \sigma(B)>\sigma(C)$$
可以由下面这些不等式保证：
$$a_1+\cdots+a_{m+1} > a_{n-m+1}+\cdots+a_n \qquad \left(m=1,2,\dots,\left\lfloor\frac{n-1}{2}\right\rfloor\right).$$
对于 \(n=7\)，只需要检查三条：
$$a_1+a_2>a_7,\qquad a_1+a_2+a_3>a_6+a_7,\qquad a_1+a_2+a_3+a_4>a_5+a_6+a_7.$$
这就是实现中最重要的快速剪枝条件，因为它用极少的代价就能排除大量不合格候选。
标准的近最优构造从六元最优特殊和集合 \(\{11,18,19,20,22,25\}\) 出发。取其中间元素 \(b=20\)，再按照经典模板构造下一层：
$$\{b\}\cup\{b+x:x\in\{11,18,19,20,22,25\}\}=\{20,31,38,39,40,42,45\}.$$
这个七元集合的总和已经是 \(255\)。这意味着它立刻给出一个非常紧的上界：任何真正更好的答案，其总和都必须严格小于 \(255\)。后续所有搜索，实际上都是在问“有没有办法击败 255”。
对 \(A=\{20,31,38,39,40,42,45\}\) 来说，上面那三条必要不等式分别是
$$20+31=51>45,\qquad 20+31+38=89>42+45=87,\qquad 20+31+38+39=128>40+42+45=127.$$
三条都成立，所以“元素更多的子集一定和更大”这一条件已经通过了。这一点非常关键，因为它说明该模板在进入更昂贵的子集求和检查之前，就已经先通过了最重要的结构性筛选。
第二条规则比第一条更微妙。我们并不需要所有子集和都彼此不同；真正被禁止的是两个互不相交、且都非空的子集出现相同的和。对于 \(n=7\)，总共有 \(2^7-1=127\) 个非空子集，因此实现会枚举每一个子集掩码 \(M\)，计算它的和 \(\sigma(M)\)，一旦发现存在两个掩码满足
$$M\cap N=\varnothing,\qquad \sigma(M)=\sigma(N)$$
就立刻判定该候选集合失败。
在速度最快的实现中，子集和不是每次从头重算，而是利用一个非常自然的递推：从掩码里删除最低位的那个已选元素，先得到更小掩码的和，再把对应元素加回来，即
$$\sigma(M)=\sigma\!\bigl(M\setminus\{\ell\}\bigr)+a_\ell.$$
由于这里的规模只有 7 个元素，这样的完全枚举并不昂贵，反而是最稳妥、最直接的正确性保证。
假设当前已经选好了一个递增前缀 \(a_1<\cdots<a_k\)，其当前和为 \(S_{\mathrm{cur}}\)，并且下一个可选值至少是 \(v\)。如果还剩 \(r=7-k\) 个元素没有选，那么最小的可能补全一定是 \(v,v+1,\dots,v+r-1\)。因此，任何完整扩展的总和都至少是
$$S_{\mathrm{cur}}+v+(v+1)+\cdots+(v+r-1)=S_{\mathrm{cur}}+rv+\frac{r(r-1)}{2}.$$
如果这个下界已经不可能优于当前最优总和，那么整个搜索分支都可以直接丢弃。完整搜索版本还会把前面提到的前缀-后缀不等式提前用于部分前缀：一旦部分前缀已经违反这些不等式，后面再加入更大的数也不可能把它修复回来。
从模板给出的上界 \(255\) 出发，穷举搜索会遍历所有理论上可能更优的严格递增七元集合，并把明显不可能成功的分支尽早剪掉。每个长度达到 7 的完整候选集合，都会被严格检查是否满足两条特殊和条件。由于最终找不到任何总和小于 255 的有效集合，于是模板本身就被证明是最优解，也就是 \(\{20,31,38,39,40,42,45\}\)，对应输出字符串 \(20313839404245\)。
C++、Python 和 Java 三个实现都把候选答案视为严格递增序列，并且都依赖同样的两层判定逻辑：先用前缀-后缀不等式检查大小规则，再用互不相交子集的求和比较检查唯一性规则。
三种语言的差别主要在搜索方式上。C++ 版本采用了完整的 branch-and-bound 搜索，并使用剩余尾部最小可能和作为强下界。Java 版本也进行递归搜索，并同样以模板总和作为起始上界，不过对下一个值使用了更简单的范围限制。Python 版本则围绕标准七元模板做一个很窄的局部扰动搜索。虽然搜索策略不完全一样，但它们最终判定候选是否有效的数学标准完全一致。
一旦某个候选达到 7 个元素，实现就会先确认它已经排序，然后应用快速大小规则，再枚举所有非空子集掩码。如果出现一对子集既互不相交又同和，当前候选会立刻被淘汰；如果它有效且总和更小，就更新当前最佳答案。
对一个固定的 \(n\) 元集合来说，大小规则检查只需要 \(O(n)\)。子集阶段需要处理 \(O(2^n)\) 个掩码，而这里采用的直接互斥对子比较同样是指数级的；保守地说，完整验证器可以视为至多 \(O(4^n)\)。但由于这里 \(n=7\)，这个成本在绝对规模上仍然很小。
外层搜索本质上也是指数型，因为它在遍历候选集合空间。真正让问题变得容易的，是上界 \(255\) 已经非常紧，再加上下界 \(S_{\mathrm{cur}}+rv+\frac{r(r-1)}{2}\) 能在进入昂贵的子集检查之前剪掉大量分支。对于这个固定的七元问题，这样的组合足以很快证明最优性。
Нужно найти строго возрастающее множество из семи положительных целых чисел \(A=\{a_1,a_2,\dots,a_7\}\) с минимально возможной суммой, которое удовлетворяет двум условиям. Во-первых, никакие два непустых непересекающихся подмножества не должны иметь одинаковую сумму. Во-вторых, если два непересекающихся подмножества имеют разную мощность, то подмножество с большим числом элементов обязано иметь и большую сумму. Оптимальное множество равно \(\{20,31,38,39,40,42,45\}\), поэтому требуемая конкатенированная строка равна \(20313839404245\).
Представленные реализации не опираются на замкнутую формулу. Они сочетают сильную структурную лемму для условия по мощностям, точную проверку равенства сумм у непересекающихся подмножеств и поиск, который стартует с шаблона, полученного из известного оптимума для 6 элементов.
Обозначим \(\sigma(B)=\sum_{x\in B}x\). После сортировки кандидата по возрастанию задача сводится к конечному поиску с сильным отсечением: одно условие превращается в несколько линейных неравенств, а второе можно проверить напрямую перебором битовых масок подмножеств.
Пусть \(a_1<a_2<\cdots<a_n\). Среди всех подмножеств размера \(m+1\) минимальная сумма равна \(a_1+\cdots+a_{m+1}\), а среди всех подмножеств размера \(m\) максимальная сумма равна \(a_{n-m+1}+\cdots+a_n\). Поэтому условие
$$|B|>|C| \Longrightarrow \sigma(B)>\sigma(C)$$
гарантируется, если выполнены лишь неравенства
$$a_1+\cdots+a_{m+1} > a_{n-m+1}+\cdots+a_n \qquad \left(m=1,2,\dots,\left\lfloor\frac{n-1}{2}\right\rfloor\right).$$
Для \(n=7\) это сокращается до трёх проверок:
$$a_1+a_2>a_7,\qquad a_1+a_2+a_3>a_6+a_7,\qquad a_1+a_2+a_3+a_4>a_5+a_6+a_7.$$
Именно это наблюдение служит самым дешёвым и самым полезным фильтром во всех версиях решения.
Стандартная почти оптимальная конструкция начинается с оптимального специального множества размера 6: \(\{11,18,19,20,22,25\}\). Его средний элемент равен \(b=20\). Шаблон для следующего размера имеет вид
$$\{b\}\cup\{b+x:x\in\{11,18,19,20,22,25\}\}=\{20,31,38,39,40,42,45\}.$$
Сумма этого множества уже равна \(255\), то есть мы сразу получаем очень жёсткую верхнюю границу: любое лучшее решение должно иметь сумму строго меньше 255. Весь поиск устроен как попытка улучшить именно эту границу.
Для \(A=\{20,31,38,39,40,42,45\}\) три необходимые проверки выглядят так:
$$20+31=51>45,\qquad 20+31+38=89>42+45=87,\qquad 20+31+38+39=128>40+42+45=127.$$
Значит, правило «большее по числу элементов подмножество должно иметь большую сумму» уже выполняется. Именно поэтому эта проверка так ценна как ранний фильтр до более дорогого перебора подмножеств.
Второе условие более тонкое. Не требуется, чтобы все суммы подмножеств были попарно различны; запрещены только совпадения у двух непустых непересекающихся подмножеств. Для \(n=7\) имеется \(2^7-1=127\) непустых подмножеств, поэтому реализации перебирают маски \(M\) и вычисляют \(\sigma(M)\). Кандидат отвергается сразу, как только находятся маски с
$$M\cap N=\varnothing,\qquad \sigma(M)=\sigma(N).$$
В самой быстрой версии суммы подмножеств строятся инкрементально, удалением младшего установленного бита, что даёт рекуррентную формулу
$$\sigma(M)=\sigma\!\bigl(M\setminus\{\ell\}\bigr)+a_\ell.$$
При размере всего 7 такая полная проверка совершенно практична.
Пусть уже выбран возрастающий префикс \(a_1<\cdots<a_k\), его текущая сумма равна \(S_{\mathrm{cur}}\), а следующее допустимое значение не меньше \(v\). Если осталось добрать \(r=7-k\) элементов, то наименьшее возможное завершение равно \(v,v+1,\dots,v+r-1\). Следовательно, любая достройка имеет суммарное значение не меньше
$$S_{\mathrm{cur}}+v+(v+1)+\cdots+(v+r-1)=S_{\mathrm{cur}}+rv+\frac{r(r-1)}{2}.$$
Если эта нижняя граница уже не может улучшить текущий лучший результат, то всю ветвь можно отбросить. Полные версии поиска также применяют префиксно-суффиксные неравенства уже к частичным префиксам: если нарушение появилось там, добавление ещё больших чисел его не исправит.
Начиная с верхней границы 255, заданной шаблоном, полный поиск перечисляет все строго возрастающие семиэлементные кандидаты, которые теоретически могут быть лучше, и рано отсекает безнадёжные ветви. Каждый полный кандидат затем проверяется на оба условия специального множества. Поскольку не находится ни одного допустимого множества с меньшей суммой, сам шаблон оказывается оптимальным. Отсюда и получается \(\{20,31,38,39,40,42,45\}\) и строка \(20313839404245\).
Реализации на C++, Python и Java рассматривают кандидаты как строго возрастающие последовательности и используют одни и те же две математические проверки: префиксно-суффиксные неравенства для правила по размерам и проверку равенства сумм у непересекающихся подмножеств для правила уникальности.
Главные различия находятся в поисковом слое. Версия на C++ выполняет полный поиск branch-and-bound с сильной арифметической нижней оценкой для ещё не достроенного хвоста. Версия на Java также идёт рекурсивно под той же верхней границей, но использует более простое ограничение на следующий элемент. Версия на Python исследует узкую окрестность стандартного семиэлементного шаблона, построенного из оптимума для 6 элементов. Во всех трёх языках судьбу кандидата определяют одни и те же условия специального множества.
Когда кандидат достигает длины 7, реализация проверяет упорядоченность, применяет быстрый фильтр по размерам, перечисляет маски всех непустых подмножеств и немедленно отвергает кандидата, если обнаруживается непересекающаяся пара с одинаковой суммой. Любое допустимое множество с меньшей общей суммой заменяет текущий лучший ответ.
Для фиксированного множества размера \(n\) проверка правила по размерам стоит \(O(n)\). Этап с подмножествами требует \(O(2^n)\) масок, а прямое сравнение непересекающихся пар, используемое здесь, тоже экспоненциально; если брать осторожную оценку, полный валидатор укладывается в \(O(4^n)\). При \(n=7\) это всё равно очень мало в абсолютном выражении.
Внешний поиск тоже принципиально экспоненциален, потому что перебирает пространство кандидатных множеств. На практике задача остаётся быстрой, потому что верхняя граница \(255\) уже очень жёсткая, а нижняя оценка \(S_{\mathrm{cur}}+rv+\frac{r(r-1)}{2}\) отсекает большие части дерева ещё до дорогой проверки подмножеств. Для фиксированного случая из семи элементов этого достаточно, чтобы быстро получить сертификат оптимальности.
نبحث عن مجموعة متزايدة من سبعة أعداد صحيحة موجبة \(A=\{a_1,a_2,\dots,a_7\}\) يكون مجموع عناصرها أصغر ما يمكن، مع تحقيق شرطين. الشرط الأول هو أنه لا يجوز أن يوجد مجموعان متساويان لمجموعتين جزئيتين غير فارغتين ومتباينتين. والشرط الثاني هو أنه إذا كانت مجموعتان جزئيتان متباينتان تختلفان في عدد العناصر، فإن المجموعة ذات العناصر الأكثر يجب أن يكون مجموعها أكبر أيضًا. المجموعة المثلى هي \(\{20,31,38,39,40,42,45\}\)، ولذلك تكون السلسلة المطلوبة بعد وصل العناصر هي \(20313839404245\).
الحلول المعطاة لا تعتمد على صيغة مغلقة مباشرة، بل تجمع بين لمّة بنيوية قوية لشرط عدد العناصر، وفحص صريح لمجاميع المجموعات الجزئية المتباينة، وبحث يبدأ من قالب سباعي مشتق من المجموعة المثلى ذات الستة عناصر.
لنكتب \(\sigma(B)=\sum_{x\in B}x\). بعد ترتيب المجموعة المرشحة تصاعديًا، تتحول المسألة إلى بحث منتهٍ مع تقليم قوي: أحد الشرطين يختزل إلى عدد قليل من المتباينات الخطية، والشرط الآخر يمكن التحقق منه تمامًا عبر تعداد أقنعة المجموعات الجزئية.
افترض أن \(a_1<a_2<\cdots<a_n\). أصغر مجموع ممكن لأي مجموعة جزئية حجمها \(m+1\) هو \(a_1+\cdots+a_{m+1}\)، وأكبر مجموع ممكن لأي مجموعة جزئية حجمها \(m\) هو \(a_{n-m+1}+\cdots+a_n\). لذلك فإن الشرط
$$|B|>|C| \Longrightarrow \sigma(B)>\sigma(C)$$
يصبح مضمونًا إذا تحقق فقط أن
$$a_1+\cdots+a_{m+1} > a_{n-m+1}+\cdots+a_n \qquad \left(m=1,2,\dots,\left\lfloor\frac{n-1}{2}\right\rfloor\right).$$
وعندما \(n=7\) لا يبقى إلا ثلاث مقارنات:
$$a_1+a_2>a_7,\qquad a_1+a_2+a_3>a_6+a_7,\qquad a_1+a_2+a_3+a_4>a_5+a_6+a_7.$$
هذه هي أداة التصفية السريعة الأساسية في جميع التطبيقات.
البناء شبه الأمثل القياسي يبدأ من المجموعة الخاصة المثلى ذات الحجم 6 وهي \(\{11,18,19,20,22,25\}\). العنصر الأوسط فيها هو \(b=20\). وعند الانتقال إلى الحجم التالي نحصل على القالب المعتاد
$$\{b\}\cup\{b+x:x\in\{11,18,19,20,22,25\}\}=\{20,31,38,39,40,42,45\}.$$
مجموع هذا القالب يساوي أصلًا \(255\)، ولذلك يعطينا مباشرة حدًا علويًا حادًا جدًا: أي حل أفضل يجب أن يكون مجموعه أصغر من \(255\). وهكذا يصبح هدف البحث هو محاولة التفوق على هذا الحد.
بالنسبة إلى \(A=\{20,31,38,39,40,42,45\}\)، تكون المقارنات الثلاث المطلوبة هي
$$20+31=51>45,\qquad 20+31+38=89>42+45=87,\qquad 20+31+38+39=128>40+42+45=127.$$
إذن شرط أن تكون المجموعة الأكبر عددًا أكبر مجموعًا متحقق بالفعل. ولهذا السبب بالتحديد يعد هذا الاختبار المبكر مرشحًا قويًا قبل الدخول في التعداد الأغلى للمجموعات الجزئية.
الشرط الثاني أدق من الأول. نحن لا نشترط أن تكون جميع مجاميع المجموعات الجزئية مختلفة؛ الممنوع فقط هو أن تتساوى مجموعتاـن جزئيتان غير فارغتين ومتباينتين. عندما \(n=7\) يوجد \(2^7-1=127\) مجموعة جزئية غير فارغة، لذا تقوم التطبيقات بتعداد القناع \(M\) وحساب \(\sigma(M)\)، ثم ترفض المرشح فور العثور على قناعين يحققان
$$M\cap N=\varnothing,\qquad \sigma(M)=\sigma(N).$$
وفي أسرع تنفيذ، تُبنى مجاميع المجموعات الجزئية تزايديًا بإزالة أقل عنصر مختار ممثلًا بأصغر بت فعّال، فنحصل على العلاقة
$$\sigma(M)=\sigma\!\bigl(M\setminus\{\ell\}\bigr)+a_\ell.$$
وبما أن عدد العناصر سبعة فقط، فإن هذا الفحص الكامل عملي جدًا.
افترض أننا اخترنا بالفعل بادئة متزايدة \(a_1<\cdots<a_k\)، وكان مجموعها الحالي \(S_{\mathrm{cur}}\)، وأن القيمة التالية يجب أن تكون على الأقل \(v\). إذا بقي \(r=7-k\) عناصر، فإن أصغر إكمال ممكن هو \(v,v+1,\dots,v+r-1\). لذلك فكل امتداد كامل يملك مجموعًا لا يقل عن
$$S_{\mathrm{cur}}+v+(v+1)+\cdots+(v+r-1)=S_{\mathrm{cur}}+rv+\frac{r(r-1)}{2}.$$
إذا كان هذا الحد السفلي لا يمكنه أصلًا أن يهزم أفضل مجموع معروف، فإن الفرع كله يُقصى. كما أن النسخ الشاملة من البحث تعيد استعمال متباينات البادئة واللاحقة على البوادئ الجزئية نفسها، لأن أي مخالفة تظهر هناك لا يمكن إصلاحها لاحقًا بإضافة أعداد أكبر.
انطلاقًا من الحد العلوي \(255\) الذي يوفره القالب، يقوم البحث الشامل بتعداد جميع المجموعات المتزايدة ذات السبعة عناصر التي يمكن نظريًا أن تكون أفضل، مع حذف الفروع الميؤوس منها مبكرًا. وبعد ذلك تُفحص كل مجموعة مكتملة مقابل الشرطين الخاصين بالمجاميع. ولأننا لا نجد أي مجموعة صالحة مجموعها أصغر، فإن القالب نفسه يكون هو الحل الأمثل. ومن هنا نحصل على \(\{20,31,38,39,40,42,45\}\) وعلى السلسلة \(20313839404245\).
تتعامل تطبيقات C++ وPython وJava مع المرشحين على أنهم متتاليات متزايدة، وتستخدم الفاحصين الرياضيين نفسيهما: متباينات البادئة واللاحقة لشرط عدد العناصر، وفحص مجاميع المجموعات الجزئية المتباينة لشرط التفرد.
الاختلاف الأساسي بين اللغات يقع في طبقة البحث. نسخة C++ تنفذ بحثًا كاملًا من نوع branch-and-bound مع حد سفلي حسابي قوي للذيل غير المكتمل. نسخة Java تبحث أيضًا بصورة عودية تحت الحد العلوي نفسه، ولكن مع نافذة أبسط للقيمة التالية. أما نسخة Python فتستكشف جوارًا ضيقًا حول القالب السباعي القياسي المشتق من الحل الأمثل ذي الستة عناصر. ومع ذلك، فإن الحكم النهائي على المرشح في اللغات الثلاث تحكمه القواعد الرياضية نفسها.
عندما يصل المرشح إلى طول 7، يتحقق التنفيذ من الترتيب أولًا، ثم يطبق مرشح الحجم السريع، ثم يعدّد جميع أقنعة المجموعات الجزئية غير الفارغة، ويرفض المرشح فور ظهور زوج متباين له المجموع نفسه. وكل مجموعة صالحة ذات مجموع أصغر تستبدل أفضل جواب معروف حتى تلك اللحظة.
بالنسبة إلى مجموعة ثابتة حجمها \(n\)، فإن اختبار شرط الحجم يكلف \(O(n)\). ومرحلة المجموعات الجزئية تحتاج إلى \(O(2^n)\) قناع، كما أن المقارنة المباشرة للأزواج المتباينة المستخدمة هنا تظل أسية؛ وبصورة محافظة يمكن اعتبار المدقق الكامل في حدود \(O(4^n)\). لكن عندما \(n=7\) يبقى ذلك صغيرًا جدًا عمليًا.
أما البحث الخارجي فهو أيضًا أسي من حيث المبدأ لأنه يستعرض فضاء المجموعات المرشحة. والسبب في بقاء المسألة سهلة عمليًا هو أن الحد العلوي \(255\) ضيق جدًا أصلًا، وأن الحد السفلي \(S_{\mathrm{cur}}+rv+\frac{r(r-1)}{2}\) يقطع أجزاء كبيرة من شجرة البحث قبل الوصول إلى فحص المجموعات الجزئية المكلف. لذلك يمكن إثبات المثالية بسرعة في هذه الحالة الثابتة ذات السبعة عناصر.