Let \(A=\{1^2,2^2,\dots,100^2\}\). Among all 50-element subsets of \(A\), some subset sums occur exactly once and others occur more than once. The task is to add precisely those sums that are realized by one and only one 50-element subset.
Brute force is hopeless because the number of 50-subsets is \(\binom{100}{50}\). The important observation is that the final answer does not depend on the exact multiplicity of a sum once that multiplicity reaches 2. We only need to know whether a sum is impossible, unique, or already non-unique.
Write \(v_i=i^2\). For each prefix \(\{v_1,\dots,v_t\}\), each subset size \(j\), and each sum \(s\), let \(C_t(j,s)\) be the number of \(j\)-element subsets of that prefix whose elements add up to \(s\). Then the quantity required by the problem is
$$\sum_{s: C_{100}(50,s)=1} s.$$
The whole solution comes from turning this exact counting function into a three-state dynamic program.
The ordinary 0/1 subset-sum recurrence with a cardinality dimension is
$$C_t(j,s)=C_{t-1}(j,s)+C_{t-1}(j-1,s-v_t).$$
The first term skips the new square \(v_t\); the second term uses it. The base condition is
$$C_0(0,0)=1,$$
because the empty subset is the unique 0-element subset with sum 0, while every other state with \(t=0\) is impossible.
The final answer only distinguishes the cases \(0\), \(1\), and \(\ge 2\). So define the saturated count
$$M_t(j,s)=\min(2,C_t(j,s))\in\{0,1,2\}.$$
Then the recurrence can be clipped after every update:
$$M_t(j,s)=\min\bigl(2,M_{t-1}(j,s)+M_{t-1}(j-1,s-v_t)\bigr).$$
This loses no relevant information. For example, among the first seven squares, the sum 62 already appears at least twice:
$$62=1+25+36=4+9+49.$$
Once a state has reached value 2, it can never become unique again, so the exact count beyond that threshold is irrelevant to the final sum.
Each square may be used at most once. Therefore, when the recurrence is implemented in place, subset sizes must be processed in descending order. That guarantees every new \(j\)-subset still reads from states representing only the first \(t-1\) squares.
The implementations also keep, for each subset size \(j\), the smallest and largest reachable sums seen so far. If the next square is \(x\), then every newly created \(j\)-subset sum that uses \(x\) must lie between
$$L_{j-1}+x \quad \text{and} \quad H_{j-1}+x,$$
where \(L_{j-1}\) and \(H_{j-1}\) are the current lower and upper bounds for \((j-1)\)-element sums. These bounds do not claim that every intermediate value is reachable; they merely bracket the active region so the inner loop skips sums that are certainly impossible.
The global table width is determined by the largest possible 50-subset sum, namely
$$S_{\max}=\sum_{i=51}^{100} i^2.$$
A small example with no collisions is the checkpoint case \(n=5\), \(k=3\), based on the set \(\{1,4,9,16,25\}\). The 3-element subset sums are
$$14,21,26,29,30,35,38,42,45,50.$$
All ten are distinct, so every reachable sum has saturated value 1 and therefore
$$U(5,3)=14+21+26+29+30+35+38+42+45+50=330.$$
This example shows the “unique” state. The earlier identity for 62 shows the “non-unique” state. Those two examples together explain why the dynamic program only needs the values 0, 1, and 2.
After all 100 squares have been processed, the desired answer is simply
$$\sum_{s: M_{100}(50,s)=1} s.$$
No subset reconstruction is required. The dynamic program has already preserved exactly the information needed to decide whether each 50-subset sum is unique.
The C++, Python, and Java implementations all realize the same mathematics. They first generate the list \(1^2,2^2,\dots,100^2\), compute the maximum possible 50-subset sum \(S_{\max}\), and allocate one flat table representing all states \((j,s)\) with \(0\le j\le 50\) and \(0\le s\le S_{\max}\).
Because every state is only 0, 1, or 2, one byte per cell is enough. For the Euler instance,
$$S_{\max}=\sum_{i=51}^{100} i^2=295425,$$
so the table contains \((50+1)(295425+1)\) cells, which is practical with byte-sized storage.
For each square \(x\), the implementation walks the subset size downward. Inside the currently relevant sum window, it reads the state for \((j-1,s-x)\), adds that contribution into the state for \((j,s)\), and then clips the result back to 2. States whose predecessor value is 0 are skipped immediately.
The size loop must go downward to preserve the 0/1 meaning of the recurrence. The sum loop is also performed in descending order inside the active window, which fits the same in-place update discipline and keeps the implementation simple.
After each square is processed, the lower and upper reachable sums for every subset size are widened only when the new square can actually create additional totals. At the end, the implementation scans the reachable window for subset size 50 and adds exactly those sums whose stored state is 1. States 0 and 2 are ignored for opposite reasons: one is impossible, the other is not unique.
Let \(k=50\) and let \(S_{\max}\) be the largest possible \(k\)-subset sum. The worst-case running time is
$$O(nkS_{\max}),$$
which is the standard pseudo-polynomial complexity of fixed-cardinality subset-sum dynamic programming. The moving lower and upper bounds reduce the amount of work in practice, but they do not change the asymptotic upper bound.
The memory usage is
$$O(kS_{\max}),$$
because only one table over subset size and sum is stored. The method is efficient precisely because it replaces an impossible search over \(\binom{100}{50}\) subsets by a structured DP over reachable sums.
Betrachte \(A=\{1^2,2^2,\dots,100^2\}\). Unter allen 50-elementigen Teilmengen von \(A\) treten manche Teilmengensummen genau einmal auf, andere mehrfach. Gesucht ist die Summe genau derjenigen Werte, die von genau einer 50-elementigen Teilmenge erzeugt werden.
Eine direkte Aufzählung aller \(\binom{100}{50}\) Teilmengen ist ausgeschlossen. Entscheidend ist, dass für die Endantwort die genaue Vielfachheit einer Summe ab dem Wert 2 keine Rolle mehr spielt. Wir müssen nur wissen, ob eine Summe unmöglich, eindeutig oder bereits nicht mehr eindeutig ist.
Setze \(v_i=i^2\). Für jedes Präfix \(\{v_1,\dots,v_t\}\), jede Teilmengengröße \(j\) und jede Summe \(s\) sei \(C_t(j,s)\) die Anzahl der \(j\)-elementigen Teilmengen dieses Präfixes mit Summe \(s\). Dann ist die gesuchte Größe
$$\sum_{s: C_{100}(50,s)=1} s.$$
Die gesamte Lösung besteht darin, diese exakte Zählfunktion in ein Drei-Zustands-DP zu überführen.
Die übliche 0/1-Teilmengensummen-Rekursion mit zusätzlicher Kardinalitätsdimension lautet
$$C_t(j,s)=C_{t-1}(j,s)+C_{t-1}(j-1,s-v_t).$$
Der erste Summand ignoriert das neue Quadrat \(v_t\), der zweite verwendet es. Die Anfangsbedingung ist
$$C_0(0,0)=1,$$
denn die leere Menge ist die einzige 0-elementige Teilmenge mit Summe 0. Alle anderen Zustände mit \(t=0\) sind unmöglich.
Für die Endantwort sind nur die Fälle \(0\), \(1\) und \(\ge 2\) relevant. Deshalb definieren wir den gesättigten Zählwert
$$M_t(j,s)=\min(2,C_t(j,s))\in\{0,1,2\}.$$
Dann darf nach jedem Schritt direkt abgeschnitten werden:
$$M_t(j,s)=\min\bigl(2,M_{t-1}(j,s)+M_{t-1}(j-1,s-v_t)\bigr).$$
Dadurch geht keine relevante Information verloren. Schon bei den ersten sieben Quadraten tritt die Summe 62 mindestens zweimal auf:
$$62=1+25+36=4+9+49.$$
Sobald ein Zustand den Wert 2 erreicht hat, kann er nie wieder eindeutig werden. Die genaue Anzahl oberhalb dieser Schwelle ist also für die Zielgröße bedeutungslos.
Jedes Quadrat darf höchstens einmal benutzt werden. Deshalb muss bei einer In-Place-Implementierung die Teilmengengröße \(j\) in absteigender Reihenfolge verarbeitet werden. Nur so lesen neue \(j\)-Teilmengen weiterhin ausschließlich Zustände, die noch das Präfix mit \(t-1\) Quadraten beschreiben.
Zusätzlich verwalten die Implementierungen für jede Größe \(j\) die kleinste und größte bisher erreichbare Summe. Ist das nächste Quadrat \(x\), dann kann jede neu entstehende \(j\)-Summe, die \(x\) benutzt, nur zwischen
$$L_{j-1}+x \quad \text{und} \quad H_{j-1}+x$$
liegen, wobei \(L_{j-1}\) und \(H_{j-1}\) die aktuellen unteren und oberen Grenzen der \((j-1)\)-Summen sind. Diese Grenzen behaupten nicht, dass jeder Zwischenwert erreichbar ist; sie fassen nur den aktiven Bereich zusammen, damit die Schleifen offensichtlich unmögliche Summen überspringen.
Die globale Tabellenbreite wird durch die größte mögliche 50-Teilmengensumme bestimmt:
$$S_{\max}=\sum_{i=51}^{100} i^2.$$
Ein kleines Beispiel ohne Kollisionen ist der Prüfpunkt \(n=5\), \(k=3\) mit der Menge \(\{1,4,9,16,25\}\). Die 3-elementigen Teilmengensummen sind
$$14,21,26,29,30,35,38,42,45,50.$$
Alle zehn Werte sind verschieden, also hat jede erreichbare Summe den gesättigten Wert 1 und damit gilt
$$U(5,3)=14+21+26+29+30+35+38+42+45+50=330.$$
Dieses Beispiel zeigt den Zustand „eindeutig“. Die Identität für 62 zeigt den Zustand „nicht eindeutig“. Genau deshalb reichen im DP die Werte 0, 1 und 2 aus.
Nachdem alle 100 Quadrate verarbeitet wurden, ist die gesuchte Antwort schlicht
$$\sum_{s: M_{100}(50,s)=1} s.$$
Eine Rekonstruktion konkreter Teilmengen ist nicht nötig. Das DP speichert bereits exakt die Information, die für die Eindeutigkeitsentscheidung benötigt wird.
Die C++-, Python- und Java-Implementierungen setzen dieselbe Mathematik um. Zuerst erzeugen sie die Liste \(1^2,2^2,\dots,100^2\), berechnen die maximale mögliche 50-Teilmengensumme \(S_{\max}\) und reservieren eine flache Tabelle für alle Zustände \((j,s)\) mit \(0\le j\le 50\) und \(0\le s\le S_{\max}\).
Da jeder Zustand nur 0, 1 oder 2 sein kann, genügt ein Byte pro Zelle. Für den Euler-Fall gilt
$$S_{\max}=\sum_{i=51}^{100} i^2=295425,$$
sodass die Tabelle \((50+1)(295425+1)\) Zellen besitzt und mit Byte-Speicherung problemlos handhabbar bleibt.
Für jedes Quadrat \(x\) läuft die Implementierung die Teilmengengröße in absteigender Reihenfolge durch. Innerhalb des jeweils relevanten Summenfensters liest sie den Zustand \((j-1,s-x)\), addiert diesen Beitrag in den Zustand \((j,s)\) und schneidet das Ergebnis anschließend wieder bei 2 ab. Zustände mit Vorgängerwert 0 werden sofort übersprungen.
Die Schleife über die Teilmengengröße muss abwärts laufen, damit die 0/1-Bedeutung der Rekursion erhalten bleibt. Auch die Summenschleife läuft innerhalb des aktiven Fensters rückwärts, was gut zu derselben In-Place-Strategie passt und die Implementierung schlicht hält.
Nach jedem Quadrat werden die unteren und oberen erreichbaren Summen jeder Teilmengengröße nur dann erweitert, wenn das neue Quadrat tatsächlich zusätzliche Summen erzeugen kann. Am Ende wird das aktive Fenster für Größe 50 abgescannt, und genau die Summen mit gespeichertem Wert 1 gehen in die Antwort ein. Zustände 0 und 2 werden aus entgegengesetzten Gründen verworfen: Die einen sind unmöglich, die anderen nicht eindeutig.
Sei \(k=50\) und \(S_{\max}\) die größte mögliche \(k\)-Teilmengensumme. Dann beträgt die Worst-Case-Laufzeit
$$O(nkS_{\max}),$$
also die übliche pseudopolynomielle Komplexität eines Teilmengensummen-DP mit fester Kardinalität. Die wandernden unteren und oberen Grenzen sparen in der Praxis viele Iterationen, ändern aber die asymptotische Schranke nicht.
Der Speicherbedarf ist
$$O(kS_{\max}),$$
weil nur eine einzige Tabelle über Teilmengengröße und Summe gehalten wird. Effizient ist die Methode gerade deshalb, weil sie die unmögliche Suche über \(\binom{100}{50}\) Teilmengen durch ein strukturiertes DP über erreichbare Summen ersetzt.
\(A=\{1^2,2^2,\dots,100^2\}\) kümesini düşünelim. Bu kümenin 50 elemanlı bütün alt kümeleri arasında bazı toplamlar yalnızca bir kez, bazı toplamlar ise birden fazla kez ortaya çıkar. İstenen şey, tam olarak tek bir 50 elemanlı alt kümeden gelen toplamların hepsini toplayabilmektir.
\(\binom{100}{50}\) farklı alt kümeyi tek tek denemek mümkün değildir. Kritik gözlem şudur: Bir toplamın temsil sayısı 2'ye ulaştıktan sonra, o sayının tam olarak kaç farklı yolla oluştuğunu bilmeye artık gerek kalmaz. Yalnızca üç durum önemlidir: imkansız, tekil ve tekil olmayan.
\(v_i=i^2\) yazalım. Her \(\{v_1,\dots,v_t\}\) öneki, her alt küme boyutu \(j\) ve her toplam \(s\) için \(C_t(j,s)\), bu önekten seçilen \(j\) elemanlı alt kümelerin toplamı \(s\) yapma sayısı olsun. O zaman problemde istenen büyüklük
$$\sum_{s: C_{100}(50,s)=1} s$$
olur. Çözümün tamamı, bu tam sayımı üç durumlu bir dinamik programa dönüştürmekten ibarettir.
Ek bir kardinalite boyutuna sahip klasik 0/1 subset-sum bağıntısı
$$C_t(j,s)=C_{t-1}(j,s)+C_{t-1}(j-1,s-v_t)$$
şeklindedir. Birinci terim yeni kare \(v_t\)'yi almayan alt kümeleri, ikinci terim ise alan alt kümeleri sayar. Başlangıç koşulu
$$C_0(0,0)=1$$
olur; çünkü boş küme, toplamı 0 olan tek 0 elemanlı alt kümedir. \(t=0\) için diğer bütün durumlar imkansızdır.
Son cevap yalnızca \(0\), \(1\) ve \(\ge 2\) durumlarını ayırt eder. Bu nedenle doygunlaştırılmış sayımı
$$M_t(j,s)=\min(2,C_t(j,s))\in\{0,1,2\}$$
diye tanımlayabiliriz. Böylece her güncellemeden sonra 2'de kesmek yeterlidir:
$$M_t(j,s)=\min\bigl(2,M_{t-1}(j,s)+M_{t-1}(j-1,s-v_t)\bigr).$$
Bu işlem gerekli bilgiyi kaybetmez. Örneğin ilk yedi karenin içinde 62 toplamı en az iki farklı şekilde elde edilir:
$$62=1+25+36=4+9+49.$$
Bir durum 2 değerine ulaştıktan sonra tekrar “tekil” hale gelemez. Bu yüzden 2'nin üzerindeki tam çokluk değeri artık son toplam için önemsizdir.
Her kare en fazla bir kez kullanılabilir. Bu nedenle bağıntı yerinde uygulanırken alt küme boyutu \(j\) mutlaka büyükten küçüğe doğru işlenmelidir. Böylece yeni oluşan her \(j\)-elemanlı durum, hâlâ yalnızca ilk \(t-1\) kareyi temsil eden durumlardan okunur.
Uygulamalar ayrıca her boyut \(j\) için o ana kadar erişilebilen en küçük ve en büyük toplamı tutar. Sonraki kare \(x\) ise, \(x\)'i kullanan yeni \(j\)-toplamları yalnızca
$$L_{j-1}+x \quad \text{ile} \quad H_{j-1}+x$$
arasına düşebilir. Burada \(L_{j-1}\) ve \(H_{j-1}\), \((j-1)\)-elemanlı toplamlar için geçerli alt ve üst sınırlardır. Bu aralık, aradaki her değerin erişilebilir olduğunu söylemez; sadece aktif bölgeyi çevreleyerek açıkça imkansız toplamların döngülerde taranmasını önler.
Küresel tablo genişliği ise mümkün olan en büyük 50-elemanlı alt küme toplamıyla belirlenir:
$$S_{\max}=\sum_{i=51}^{100} i^2.$$
Çakışma içermeyen küçük bir örnek, \(\{1,4,9,16,25\}\) kümesine karşılık gelen \(n=5\), \(k=3\) durumudur. 3 elemanlı alt küme toplamları
$$14,21,26,29,30,35,38,42,45,50$$
şeklindedir. Bu on toplamın hepsi farklı olduğu için her erişilebilir durumun doygun değeri 1'dir ve
$$U(5,3)=14+21+26+29+30+35+38+42+45+50=330$$
elde edilir. Bu örnek “tekil” durumu gösterir. 62 eşitliği ise “tekil olmayan” durumu gösterir. Dolayısıyla dinamik programın neden yalnızca 0, 1 ve 2 değerlerine ihtiyaç duyduğu açık hale gelir.
Bütün 100 kare işlendiğinde istenen cevap doğrudan
$$\sum_{s: M_{100}(50,s)=1} s$$
olur. Alt kümeleri yeniden kurmaya gerek yoktur. Dinamik program, her 50-elemanlı toplamın tekil olup olmadığını söylemek için gereken bilgiyi zaten saklamıştır.
C++, Python ve Java uygulamalarının matematiği aynıdır. Önce \(1^2,2^2,\dots,100^2\) listesi üretilir, sonra mümkün olan en büyük 50-elemanlı toplam \(S_{\max}\) hesaplanır ve \(0\le j\le 50\), \(0\le s\le S_{\max}\) durumlarının tamamını temsil eden düz bir tablo ayrılır.
Her hücre yalnızca 0, 1 veya 2 tuttuğu için hücre başına bir byte yeterlidir. Euler örneğinde
$$S_{\max}=\sum_{i=51}^{100} i^2=295425$$
olduğundan tablo \((50+1)(295425+1)\) hücre içerir ve byte tabanlı saklama ile pratik kalır.
Her kare \(x\) için uygulama alt küme boyutunu geriye doğru gezer. İlgili toplam penceresi içinde \((j-1,s-x)\) durumunu okur, bu katkıyı \((j,s)\) durumuna ekler ve sonucu tekrar 2'de keser. Önceki değeri 0 olan durumlar hemen atlanır.
Alt küme boyutu döngüsünün aşağı yönde ilerlemesi, bağıntının 0/1 anlamını korumak için zorunludur. Toplam döngüsü de etkin pencere içinde aşağı yönde yürütülür; bu, aynı yerinde güncelleme disiplinine uyar ve uygulamayı sade tutar.
Her kareden sonra, her alt küme boyutu için alt ve üst erişilebilir toplam sınırları yalnızca yeni kare gerçekten yeni toplamlar üretebiliyorsa genişletilir. Son aşamada boyut 50 için etkin pencere taranır ve saklanan değeri 1 olan toplamlar cevaba eklenir. 0 ve 2 durumları ise zıt nedenlerle dışarıda bırakılır: biri imkansızdır, diğeri tekil değildir.
\(k=50\) ve \(S_{\max}\) en büyük olası \(k\)-elemanlı toplam olsun. O halde en kötü durum çalışma süresi
$$O(nkS_{\max})$$
olur; bu, sabit kardinaliteli subset-sum DP'nin standart pseudo-polynomial karmaşıklığıdır. Hareketli alt ve üst sınırlar pratikte ciddi tasarruf sağlar, fakat asimptotik üst sınırı değiştirmez.
Bellek kullanımı
$$O(kS_{\max})$$
düzeyindedir; çünkü yalnızca alt küme boyutu ve toplam üzerinde tek bir tablo tutulur. Yöntem etkilidir, çünkü \(\binom{100}{50}\) alt kümeyi imkansız biçimde gezmek yerine erişilebilir toplamlar üzerinde yapısal bir DP kullanır.
Sea \(A=\{1^2,2^2,\dots,100^2\}\). Entre todos los subconjuntos de 50 elementos de \(A\), algunas sumas aparecen exactamente una vez y otras aparecen varias veces. El objetivo es sumar precisamente aquellas sumas que son producidas por un único subconjunto de 50 elementos.
Enumerar directamente los \(\binom{100}{50}\) subconjuntos es inviable. La observación decisiva es que, una vez que la multiplicidad de una suma alcanza 2, ya no hace falta conocer el conteo exacto. Solo importan tres estados: imposible, único y no único.
Escribamos \(v_i=i^2\). Para cada prefijo \(\{v_1,\dots,v_t\}\), cada tamaño de subconjunto \(j\) y cada suma \(s\), sea \(C_t(j,s)\) el número de subconjuntos de tamaño \(j\) dentro de ese prefijo cuya suma es \(s\). Entonces la cantidad pedida por el problema es
$$\sum_{s: C_{100}(50,s)=1} s.$$
Toda la solución consiste en convertir esta función de conteo exacta en un DP de tres estados.
La recurrencia habitual de subset sum 0/1 con una dimensión extra de cardinalidad es
$$C_t(j,s)=C_{t-1}(j,s)+C_{t-1}(j-1,s-v_t).$$
El primer término omite el nuevo cuadrado \(v_t\); el segundo lo usa. La condición inicial es
$$C_0(0,0)=1,$$
porque el subconjunto vacío es el único subconjunto de tamaño 0 con suma 0. Todos los demás estados con \(t=0\) son imposibles.
La respuesta final solo distingue entre \(0\), \(1\) y \(\ge 2\). Por eso definimos el conteo saturado
$$M_t(j,s)=\min(2,C_t(j,s))\in\{0,1,2\}.$$
Con esta definición, después de cada actualización podemos truncar inmediatamente:
$$M_t(j,s)=\min\bigl(2,M_{t-1}(j,s)+M_{t-1}(j-1,s-v_t)\bigr).$$
No se pierde información relevante. Por ejemplo, entre los primeros siete cuadrados, la suma 62 ya aparece al menos dos veces:
$$62=1+25+36=4+9+49.$$
En cuanto un estado alcanza el valor 2, nunca podrá volver a ser único. Por eso el conteo exacto por encima de ese umbral deja de importar para la suma final.
Cada cuadrado puede usarse como máximo una vez. Por tanto, al implementar la recurrencia in place, el tamaño del subconjunto \(j\) debe recorrerse en orden descendente. Así, cada nuevo subconjunto de tamaño \(j\) sigue leyendo estados que representan solo a los primeros \(t-1\) cuadrados.
Además, las implementaciones mantienen, para cada tamaño \(j\), la menor y la mayor suma alcanzable hasta ese momento. Si el siguiente cuadrado es \(x\), entonces cualquier nueva suma de tamaño \(j\) que use \(x\) debe caer entre
$$L_{j-1}+x \quad \text{y} \quad H_{j-1}+x,$$
donde \(L_{j-1}\) y \(H_{j-1}\) son las cotas inferior y superior actuales de las sumas de tamaño \(j-1\). Estas cotas no afirman que todos los valores intermedios sean alcanzables; solo encierran la región activa para evitar recorrer sumas claramente imposibles.
La anchura global de la tabla viene dada por la mayor suma posible de un subconjunto de 50 elementos:
$$S_{\max}=\sum_{i=51}^{100} i^2.$$
Un ejemplo pequeño sin colisiones es el caso de control \(n=5\), \(k=3\), basado en \(\{1,4,9,16,25\}\). Las sumas de los subconjuntos de 3 elementos son
$$14,21,26,29,30,35,38,42,45,50.$$
Las diez son distintas, de modo que cada suma alcanzable tiene valor saturado 1 y por tanto
$$U(5,3)=14+21+26+29+30+35+38+42+45+50=330.$$
Este ejemplo muestra el estado “único”. La identidad para 62 muestra el estado “no único”. Juntos explican por qué el DP solo necesita los valores 0, 1 y 2.
Después de procesar los 100 cuadrados, la respuesta buscada es simplemente
$$\sum_{s: M_{100}(50,s)=1} s.$$
No hace falta reconstruir los subconjuntos. El DP ya ha conservado exactamente la información necesaria para decidir si cada suma de 50 elementos es única.
Las implementaciones en C++, Python y Java realizan exactamente la misma matemática. Primero generan la lista \(1^2,2^2,\dots,100^2\), calculan la suma máxima posible de un subconjunto de 50 elementos \(S_{\max}\) y reservan una tabla plana para todos los estados \((j,s)\) con \(0\le j\le 50\) y \(0\le s\le S_{\max}\).
Como cada estado solo puede ser 0, 1 o 2, basta un byte por celda. Para la instancia de Euler,
$$S_{\max}=\sum_{i=51}^{100} i^2=295425,$$
de modo que la tabla tiene \((50+1)(295425+1)\) celdas y sigue siendo manejable con almacenamiento de un byte.
Para cada cuadrado \(x\), la implementación recorre el tamaño del subconjunto en orden descendente. Dentro de la ventana de sumas actualmente relevante, lee el estado \((j-1,s-x)\), añade esa contribución al estado \((j,s)\) y luego vuelve a truncar el resultado a 2. Los estados cuyo predecesor vale 0 se descartan de inmediato.
El recorrido descendente sobre el tamaño del subconjunto es imprescindible para conservar la interpretación 0/1 de la recurrencia. El bucle sobre las sumas también se ejecuta hacia abajo dentro de la ventana activa, lo que encaja con la misma disciplina de actualización in place y mantiene la implementación limpia.
Después de cada cuadrado, las cotas inferior y superior de las sumas alcanzables para cada tamaño solo se amplían cuando el nuevo cuadrado puede producir totales adicionales. Al final, la implementación recorre la ventana activa correspondiente al tamaño 50 y suma exactamente aquellas cantidades cuyo estado almacenado es 1. Los estados 0 y 2 se excluyen por razones opuestas: uno es imposible y el otro no es único.
Sea \(k=50\) y sea \(S_{\max}\) la mayor suma posible de un subconjunto de tamaño \(k\). Entonces el tiempo de ejecución en el peor caso es
$$O(nkS_{\max}),$$
la complejidad pseudopolinómica estándar de un DP de subset sum con cardinalidad fija. Las cotas móviles reducen mucho el trabajo práctico, pero no cambian la cota asintótica.
El uso de memoria es
$$O(kS_{\max}),$$
porque solo se mantiene una tabla sobre tamaño de subconjunto y suma. El método es eficiente precisamente porque sustituye la enumeración imposible de \(\binom{100}{50}\) subconjuntos por un DP estructurado sobre sumas alcanzables.
设 \(A=\{1^2,2^2,\dots,100^2\}\)。在 \(A\) 的所有 50 元子集中，有些子集和只出现一次，有些则会由多个不同的 50 元子集得到。题目要求把所有“恰好只出现一次”的和全部相加。
直接枚举 \(\binom{100}{50}\) 个子集显然不可行。真正关键的观察是：某个和一旦已经有至少两种表示方式，就不必再关心它到底出现了几次。对最终答案来说，只需要区分三种状态：不可达、唯一、以及非唯一。
记 \(v_i=i^2\)。对每个前缀 \(\{v_1,\dots,v_t\}\)、每个子集大小 \(j\) 和每个和 \(s\)，定义 \(C_t(j,s)\) 为“从这个前缀中选出 \(j\) 个平方数且总和为 \(s\) 的方案数”。那么题目所求就是
$$\sum_{s: C_{100}(50,s)=1} s.$$
整套解法的核心，就是把这个精确计数函数改写成只含三种取值的动态规划。
带有“选取个数”这一维的标准 0/1 subset-sum 递推为
$$C_t(j,s)=C_{t-1}(j,s)+C_{t-1}(j-1,s-v_t).$$
第一项表示不选新加入的平方 \(v_t\)，第二项表示选择它。初始条件是
$$C_0(0,0)=1,$$
因为空集是唯一一个元素个数为 0、和也为 0 的子集；当 \(t=0\) 时，其余状态全部不可能出现。
最终答案只关心 \(0\)、\(1\) 和 \(\ge 2\) 这三类情况，因此可以定义饱和计数
$$M_t(j,s)=\min(2,C_t(j,s))\in\{0,1,2\}.$$
这样每次更新后都可以立刻截断到 2：
$$M_t(j,s)=\min\bigl(2,M_{t-1}(j,s)+M_{t-1}(j-1,s-v_t)\bigr).$$
这样做不会丢失与题目相关的信息。例如，只看前七个平方数时，和 62 就已经至少出现两次：
$$62=1+25+36=4+9+49.$$
一旦某个状态达到 2，它以后就再也不可能回到“唯一”。因此，2 以上的精确计数对最后要求的和已经没有任何额外价值。
每个平方数最多只能使用一次。所以当递推用原地方式实现时，子集大小 \(j\) 必须按从大到小的顺序更新。只有这样，新得到的 \(j\) 元状态才一定仍然读取的是“前 \(t-1\) 个平方数”对应的旧状态。
实现中还会为每个子集大小 \(j\) 维护当前可达和的最小值和最大值。若下一个平方是 \(x\)，那么所有“使用了 \(x\)”的新 \(j\) 元和，只可能落在
$$L_{j-1}+x \quad \text{到} \quad H_{j-1}+x$$
之间，其中 \(L_{j-1}\) 和 \(H_{j-1}\) 是当前 \((j-1)\) 元和的下界与上界。这里维护的是包住活跃状态的区间，而不是声称区间内每个值都一定可达。区间内部仍然可能有空洞，但区间外的值则肯定不必扫描。
整个表的宽度由可能出现的最大 50 元子集和决定：
$$S_{\max}=\sum_{i=51}^{100} i^2.$$
一个没有碰撞的小例子是检查用的 \(n=5\)、\(k=3\)，对应集合 \(\{1,4,9,16,25\}\)。所有 3 元子集和为
$$14,21,26,29,30,35,38,42,45,50.$$
这 10 个值全部不同，因此每个可达状态的饱和值都是 1，于是
$$U(5,3)=14+21+26+29+30+35+38+42+45+50=330.$$
这个例子展示了“唯一”状态；上面的 62 则展示了“非唯一”状态。两者合起来，正好说明为什么整个算法只需要记录 0、1、2 三种值。
当 100 个平方数全部处理完以后，所求答案就是
$$\sum_{s: M_{100}(50,s)=1} s.$$
不需要回溯具体是哪一个子集。动态规划表中已经保留了判断“某个 50 元子集和是否唯一”所需的全部信息。
C++、Python 和 Java 三个实现使用的是完全相同的数学思路。它们先生成 \(1^2,2^2,\dots,100^2\) 的列表，计算 50 元子集可能达到的最大和 \(S_{\max}\)，然后为所有满足 \(0\le j\le 50\)、\(0\le s\le S_{\max}\) 的状态 \((j,s)\) 分配一张扁平化的表。
由于每个状态只可能是 0、1、2，所以每个单元用 1 个字节就足够。对 Euler 这一组参数，
$$S_{\max}=\sum_{i=51}^{100} i^2=295425,$$
因此表的大小是 \((50+1)(295425+1)\) 个单元，用字节存储仍然完全可行。
对每个平方数 \(x\)，实现都会把子集大小按降序扫描。在当前活跃的和区间里，读取状态 \((j-1,s-x)\)，把它的贡献加到 \((j,s)\) 上，再把结果截断回 2。若前驱状态本来就是 0，则该位置会被立刻跳过。
子集大小这一层必须倒序更新，才能保持 0/1 选择的含义不变。和的循环也在活跃区间内按降序进行，这与同样的原地更新思路一致，代码结构也更清晰。
每处理完一个平方数，各个子集大小的可达和下界、上界只会在新平方确实能够带来新和时才被扩张。最后，程序只扫描 50 元子集对应的活跃区间，把所有状态恰好等于 1 的和加入答案。状态 0 和状态 2 都不会贡献：前者表示不可达，后者表示不唯一。
设 \(k=50\)，设 \(S_{\max}\) 为大小为 \(k\) 的子集可能达到的最大和。那么最坏情况下的时间复杂度为
$$O(nkS_{\max}),$$
这正是固定基数 subset-sum 动态规划的标准伪多项式复杂度。动态维护的上下界会在实际运行中显著减少扫描量，但不会改变这个渐近上界。
空间复杂度为
$$O(kS_{\max}),$$
因为程序只保存一张“子集大小 + 和”的表。这个方法之所以有效，正是因为它把不可能直接枚举的 \(\binom{100}{50}\) 个子集，转化成了一个在可达和空间上的结构化动态规划问题。
Рассмотрим множество \(A=\{1^2,2^2,\dots,100^2\}\). Среди всех его 50-элементных подмножеств некоторые суммы встречаются ровно один раз, а некоторые возникают у нескольких разных подмножеств. Требуется просуммировать именно те значения, которые реализуются единственным 50-элементным подмножеством.
Перебор всех \(\binom{100}{50}\) вариантов невозможен. Главная идея состоит в том, что после достижения кратности 2 точное число представлений уже не важно. Для окончательного ответа нужно различать только три состояния: сумма недостижима, сумма единственна, сумма уже не единственна.
Обозначим \(v_i=i^2\). Для каждого префикса \(\{v_1,\dots,v_t\}\), каждого размера подмножества \(j\) и каждой суммы \(s\) пусть \(C_t(j,s)\) означает число \(j\)-элементных подмножеств этого префикса с суммой \(s\). Тогда искомая величина равна
$$\sum_{s: C_{100}(50,s)=1} s.$$
Вся конструкция решения состоит в том, чтобы заменить эту точную функцию подсчета трехсостоянием динамического программирования.
Стандартная 0/1-рекуррентность subset sum с дополнительным измерением по мощности имеет вид
$$C_t(j,s)=C_{t-1}(j,s)+C_{t-1}(j-1,s-v_t).$$
Первое слагаемое пропускает новый квадрат \(v_t\), второе использует его. Начальное условие таково:
$$C_0(0,0)=1,$$
поскольку пустое множество является единственным подмножеством размера 0 с суммой 0. Все остальные состояния при \(t=0\) невозможны.
Окончательный ответ различает только случаи \(0\), \(1\) и \(\ge 2\). Поэтому вводится насыщенный счетчик
$$M_t(j,s)=\min(2,C_t(j,s))\in\{0,1,2\}.$$
После этого каждый шаг можно сразу обрезать по 2:
$$M_t(j,s)=\min\bigl(2,M_{t-1}(j,s)+M_{t-1}(j-1,s-v_t)\bigr).$$
Никакой существенной информации при этом не теряется. Уже среди первых семи квадратов сумма 62 появляется как минимум двумя способами:
$$62=1+25+36=4+9+49.$$
Как только состояние достигло значения 2, оно уже никогда не станет «уникальным» снова. Значит, точная кратность выше этого порога для итоговой суммы не важна.
Каждый квадрат можно взять не более одного раза. Поэтому при реализации рекуррентности in place размер подмножества \(j\) обязан обрабатываться в порядке убывания. Тогда каждое новое состояние размера \(j\) все еще читает только те значения, которые соответствуют первым \(t-1\) квадратам.
Кроме того, реализации поддерживают для каждого размера \(j\) минимальную и максимальную достижимые суммы на текущем шаге. Если следующий квадрат равен \(x\), то каждая новая сумма размера \(j\), использующая \(x\), может лежать только между
$$L_{j-1}+x \quad \text{и} \quad H_{j-1}+x,$$
где \(L_{j-1}\) и \(H_{j-1}\) обозначают текущие нижнюю и верхнюю границы для сумм размера \(j-1\). Эти границы не означают, что все промежуточные значения достижимы; они лишь охватывают активную область, чтобы внутренние циклы не просматривали заведомо невозможные суммы.
Глобальная ширина таблицы задается максимальной возможной суммой 50-элементного подмножества:
$$S_{\max}=\sum_{i=51}^{100} i^2.$$
Небольшой пример без коллизий - это проверочный случай \(n=5\), \(k=3\), то есть множество \(\{1,4,9,16,25\}\). Суммы всех 3-элементных подмножеств равны
$$14,21,26,29,30,35,38,42,45,50.$$
Все десять значений различны, значит каждое достижимое состояние имеет насыщенное значение 1 и потому
$$U(5,3)=14+21+26+29+30+35+38+42+45+50=330.$$
Этот пример иллюстрирует состояние «уникально». Тождество для 62 показывает состояние «не уникально». Вместе они объясняют, почему динамической программе достаточно значений 0, 1 и 2.
После обработки всех 100 квадратов искомый ответ просто равен
$$\sum_{s: M_{100}(50,s)=1} s.$$
Восстанавливать сами подмножества не нужно. Таблица DP уже хранит ровно ту информацию, которая требуется, чтобы определить уникальность каждой суммы из 50 элементов.
Реализации на C++, Python и Java используют одну и ту же математику. Сначала строится список \(1^2,2^2,\dots,100^2\), затем вычисляется максимальная возможная сумма 50-элементного подмножества \(S_{\max}\), после чего выделяется одна плоская таблица для всех состояний \((j,s)\) при \(0\le j\le 50\) и \(0\le s\le S_{\max}\).
Поскольку каждое состояние принимает только значения 0, 1 или 2, на одну ячейку достаточно одного байта. Для параметров задачи Euler
$$S_{\max}=\sum_{i=51}^{100} i^2=295425,$$
поэтому таблица содержит \((50+1)(295425+1)\) ячеек и остается практичной при байтовом хранении.
Для каждого квадрата \(x\) реализация проходит размер подмножества в убывающем порядке. Внутри текущего активного окна сумм она читает состояние \((j-1,s-x)\), добавляет этот вклад в состояние \((j,s)\) и затем снова обрезает результат по 2. Состояния с нулевым значением предшественника мгновенно пропускаются.
Убывающий проход по размеру подмножества необходим, чтобы сохранить 0/1-смысл рекуррентности. Цикл по суммам тоже выполняется в убывающем порядке внутри активного окна; это согласуется с той же дисциплиной in-place обновления и делает реализацию прямой.
После обработки каждого квадрата нижняя и верхняя достижимые суммы для каждого размера расширяются только тогда, когда новый квадрат действительно способен породить новые суммы. В конце просматривается активное окно для размера 50, и в ответ добавляются только те суммы, у которых сохраненное состояние равно 1. Состояния 0 и 2 отбрасываются по противоположным причинам: одно недостижимо, другое не уникально.
Пусть \(k=50\), а \(S_{\max}\) - максимальная возможная сумма \(k\)-элементного подмножества. Тогда время работы в худшем случае равно
$$O(nkS_{\max}),$$
то есть это стандартная псевдополиномиальная сложность динамики subset sum с фиксированной мощностью. Движущиеся нижние и верхние границы заметно уменьшают объем работы на практике, но не меняют асимптотическую верхнюю оценку.
Память составляет
$$O(kS_{\max}),$$
потому что хранится только одна таблица по размеру подмножества и сумме. Эффективность метода именно в том, что он заменяет невозможный перебор \(\binom{100}{50}\) подмножеств структурированным DP по достижимым суммам.
لنأخذ المجموعة \(A=\{1^2,2^2,\dots,100^2\}\). بين جميع المجموعات الجزئية ذات 50 عنصرًا من \(A\)، توجد مجاميع تظهر مرة واحدة فقط، ومجاميع أخرى تظهر أكثر من مرة. المطلوب هو جمع كل القيم التي تتحقق بواسطة مجموعة جزئية وحيدة من الحجم 50.
العدّ المباشر لجميع \(\binom{100}{50}\) مجموعة جزئية غير ممكن عمليًا. الفكرة الحاسمة هي أن المجموع متى وصل عدد تمثيلاته إلى 2، فلا تعود التفاصيل الدقيقة فوق هذا الحد مهمة. بالنسبة إلى الجواب النهائي نحتاج فقط إلى التمييز بين ثلاث حالات: غير ممكن، وحيد، وغير وحيد.
لنكتب \(v_i=i^2\). لكل بادئة \(\{v_1,\dots,v_t\}\)، ولكل حجم مجموعة جزئية \(j\)، ولكل مجموع \(s\)، نرمز بـ \(C_t(j,s)\) إلى عدد المجموعات الجزئية ذات \(j\) عنصرًا داخل هذه البادئة والتي يساوي مجموع عناصرها \(s\). عندئذ تكون الكمية المطلوبة هي
$$\sum_{s: C_{100}(50,s)=1} s.$$
جوهر الحل كله هو تحويل دالة العد الدقيقة هذه إلى برمجة ديناميكية بثلاث حالات فقط.
العلاقة العودية القياسية لمسألة subset sum من نوع 0/1 مع بعد إضافي لحجم المجموعة هي
$$C_t(j,s)=C_{t-1}(j,s)+C_{t-1}(j-1,s-v_t).$$
الحد الأول يعني عدم أخذ المربع الجديد \(v_t\)، والحد الثاني يعني أخذه. أما شرط البداية فهو
$$C_0(0,0)=1,$$
لأن المجموعة الفارغة هي المجموعة الوحيدة ذات صفر عنصر ومجموعها 0. وكل الحالات الأخرى عندما \(t=0\) تكون مستحيلة.
الجواب النهائي يميز فقط بين القيم \(0\) و\(1\) و\(\ge 2\). لذلك نعرّف العد المشبع
$$M_t(j,s)=\min(2,C_t(j,s))\in\{0,1,2\}.$$
وبذلك يمكن قص النتيجة عند 2 بعد كل تحديث:
$$M_t(j,s)=\min\bigl(2,M_{t-1}(j,s)+M_{t-1}(j-1,s-v_t)\bigr).$$
هذا لا يفقد أي معلومة مهمة للمسألة. فمثلًا، بين أول سبعة مربعات فقط، يظهر المجموع 62 بطريقتين على الأقل:
$$62=1+25+36=4+9+49.$$
وبمجرد أن تصل الحالة إلى القيمة 2، فلن تعود أبدًا حالة فريدة. لذلك لا تعود قيمة العد الدقيقة فوق هذا الحد ذات أي أثر على المجموع النهائي المطلوب.
كل مربع يمكن استعماله مرة واحدة على الأكثر. لهذا السبب، عند تنفيذ العلاقة العودية بشكل موضعي داخل الجدول نفسه، يجب معالجة حجم المجموعة \(j\) بترتيب تنازلي. عندها فقط تبقى كل حالة جديدة بحجم \(j\) معتمدة على حالات ما زالت تمثل البادئة التي تضم أول \(t-1\) مربعًا فقط.
وتحافظ التطبيقات أيضًا، لكل حجم \(j\)، على أصغر مجموع قابل للوصول وأكبره حتى اللحظة. فإذا كان المربع التالي هو \(x\)، فإن أي مجموع جديد من الحجم \(j\) يستخدم \(x\) لا بد أن يقع بين
$$[L_{j-1}+x,\ H_{j-1}+x].$$
حيث \(L_{j-1}\) و\(H_{j-1}\) هما الحد الأدنى والحد الأقصى الحاليان لمجاميع الحجم \(j-1\). هذه الحدود لا تعني أن كل قيمة بينهما قابلة للتحقق؛ بل هي فقط تطوق المنطقة النشطة حتى لا تمسح الحلقات الداخلية مجاميع مستحيلة بوضوح.
أما عرض الجدول الكلي فيحدده أكبر مجموع ممكن لمجموعة جزئية من 50 عنصرًا:
$$S_{\max}=\sum_{i=51}^{100} i^2.$$
يوجد مثال صغير بلا تصادمات هو حالة الفحص \(n=5\)، \(k=3\)، المبنية على المجموعة \(\{1,4,9,16,25\}\). مجاميع المجموعات الجزئية ذات 3 عناصر هي
$$14,21,26,29,30,35,38,42,45,50.$$
كل هذه القيم العشر مختلفة، ولذلك تكون القيمة المشبعة لكل مجموع ممكن هي 1، ومن ثم
$$U(5,3)=14+21+26+29+30+35+38+42+45+50=330.$$
هذا المثال يوضح حالة “الفريد”. أما مساواة 62 السابقة فتوضح حالة “غير الفريد”. وباجتماعهما يصبح واضحًا لماذا لا تحتاج البرمجة الديناميكية إلا إلى القيم 0 و1 و2.
بعد معالجة جميع المربعات المئة، تصبح الإجابة المطلوبة ببساطة
$$\sum_{s: M_{100}(50,s)=1} s.$$
ولا حاجة إلى إعادة بناء المجموعات الجزئية نفسها. فالجدول الديناميكي احتفظ مسبقًا بكل ما يلزم لتحديد ما إذا كان كل مجموع من الحجم 50 فريدًا أم لا.
تنفذ تطبيقات C++ وPython وJava الفكرة الرياضية نفسها حرفيًا. فهي تبدأ بتوليد القائمة \(1^2,2^2,\dots,100^2\)، ثم تحسب أكبر مجموع ممكن لمجموعة جزئية من 50 عنصرًا وهو \(S_{\max}\)، ثم تخصص جدولًا مسطحًا يمثل جميع الحالات \((j,s)\) حيث \(0\le j\le 50\) و\(0\le s\le S_{\max}\).
بما أن كل حالة لا يمكن أن تكون إلا 0 أو 1 أو 2، فإن بايتًا واحدًا لكل خلية يكفي. في حالة مسألة Euler نحصل على
$$S_{\max}=\sum_{i=51}^{100} i^2=295425,$$
ومن ثم يحتوي الجدول على \((50+1)(295425+1)\) خلية، وهو حجم عملي ما دامت كل خلية مخزنة في بايت واحد.
لكل مربع \(x\)، تمر الشيفرة على أحجام المجموعات بترتيب تنازلي. وداخل نافذة المجاميع الفعالة الحالية، تقرأ الحالة \((j-1,s-x)\)، وتضيف مساهمتها إلى الحالة \((j,s)\)، ثم تعيد قص النتيجة عند 2. وإذا كانت الحالة السابقة تساوي 0، يجري تجاوزها مباشرة.
يجب أن يكون المرور التنازلي على حجم المجموعة موجودًا للحفاظ على معنى 0/1 في العلاقة العودية. كما أن حلقة المجاميع نفسها تُنفذ أيضًا ترتيبًا تنازليًا داخل النافذة النشطة، وهذا منسجم مع أسلوب التحديث الموضعي نفسه ويجعل التنفيذ مباشرًا.
بعد كل مربع جديد، لا تتسع الحدود الدنيا والعليا للمجاميع الممكنة لكل حجم إلا إذا كان هذا المربع قادرًا فعلًا على إنشاء مجاميع إضافية. وفي النهاية تمسح الشيفرة النافذة النشطة الخاصة بالحجم 50 وتجمع فقط تلك المجاميع التي حالتها المخزنة تساوي 1. أما الحالتان 0 و2 فتُهملان لأسباب متعاكسة: الأولى مستحيلة والثانية غير فريدة.
إذا رمزنا بـ \(k=50\) وبـ \(S_{\max}\) إلى أكبر مجموع ممكن لمجموعة جزئية من الحجم \(k\)، فإن زمن التنفيذ في أسوأ الحالات يساوي
$$O(nkS_{\max}),$$
وهو التعقيد شبه كثير الحدود القياسي لبرمجة subset sum الديناميكية مع حجم ثابت للمجموعة. الحدود الدنيا والعليا المتحركة توفر الكثير من العمل عمليًا، لكنها لا تغير الحد الأعلى asymptotically.
أما استهلاك الذاكرة فيساوي
$$O(kS_{\max}),$$
لأننا نخزن جدولًا واحدًا فقط على بعدي حجم المجموعة والمجموع. وتنبع فعالية الطريقة من أنها تستبدل تعدادًا مستحيلًا لـ \(\binom{100}{50}\) مجموعة جزئية ببرمجة ديناميكية منظمة على فضاء المجاميع الممكنة.