Let \(f_0=1\), \(f_1=2\), and \(f_{k+2}=f_{k+1}+f_k\). For a given bound \(N\), keep every term \(f_i\le N\). We must count how many subsets of this finite Fibonacci-like set have total sum at most \(N\).
If \(m\) is the largest index with \(f_m\le N\), then the target quantity is
$$S(N)=\#\left\{B\subseteq \{f_0,f_1,\dots,f_m\}:\sum_{x\in B}x\le N\right\}.$$
The title "Not Zeckendorf" signals that we are not restricting ourselves to the unique nonconsecutive Fibonacci representation of each integer. Every subset is allowed, so different subsets may produce the same sum, for example \(3\) and \(1+2\).
The implementation solves the problem by recursive decomposition together with an exact pruning rule based on prefix sums.
The recurrence \(f_{k+2}=f_{k+1}+f_k\) makes the sequence grow exponentially, so only \(O(\log N)\) terms are relevant. Once the largest usable index \(m\) is found, the whole problem becomes a subset-counting question on the finite set \(\{f_0,\dots,f_m\}\).
This matters because the original input \(N\) can be huge, but the number of candidate terms stays small enough for a state-based recursion.
For \(-1\le i\le m\) and \(L\ge 0\), define
$$C(i,L)=\#\left\{B\subseteq \{f_0,f_1,\dots,f_i\}:\sum_{x\in B}x\le L\right\}.$$
This means: among the first \(i+1\) terms, how many subsets stay within budget \(L\)? The desired answer is simply
$$S(N)=C(m,N).$$
The empty-set convention gives the base case
$$C(-1,L)=1,$$
because when no terms remain, only the empty subset survives.
Every admissible subset of \(\{f_0,\dots,f_i\}\) either avoids \(f_i\) or includes it.
If \(f_i\) is not chosen, the count is \(C(i-1,L)\).
If \(f_i\) is chosen, then the remaining elements must fit inside the reduced limit \(L-f_i\), which contributes \(C(i-1,L-f_i)\), but only when \(L\ge f_i\).
Therefore
$$C(i,L)= \begin{cases} C(i-1,L), & L<f_i,\\ C(i-1,L)+C(i-1,L-f_i), & L\ge f_i. \end{cases}$$
This is the exact include-or-exclude recurrence implemented in all three languages.
Let
$$P_i=\sum_{j=0}^{i} f_j.$$
If \(L\ge P_i\), then even the subset containing every available term has sum at most \(L\). Hence every subset is feasible, so we get the closed form
$$C(i,L)=2^{i+1}\qquad\text{whenever}\qquad L\ge P_i.$$
This shortcut is exact, not heuristic. It prunes entire subtrees of the recursion.
For this particular sequence, the prefix sums also satisfy
$$P_i=f_{i+2}-2,$$
which follows by induction from the same Fibonacci-style recurrence. The implementations compute the prefix sums directly, then apply the cutoff test during recursion.
Different decision paths can lead to the same pair \((i,L)\). Once we know the largest usable index and the remaining budget, the earlier history no longer matters. Therefore the state graph is a directed acyclic graph rather than a tree of unrelated branches.
Memoization turns this observation into an exact algorithm: each distinct state \((i,L)\) is solved once, stored, and reused whenever it reappears.
The usable terms are
$$1,\ 2,\ 3,\ 5,\ 8,$$
so the prefix sums are
$$1,\ 3,\ 6,\ 11,\ 19.$$
We want \(S(10)=C(4,10)\). Since \(10<19\), split on \(8\):
$$C(4,10)=C(3,10)+C(3,2).$$
For the first term, \(10<11\), so split on \(5\):
$$C(3,10)=C(2,10)+C(2,5).$$
Now \(10\ge 6\), hence
$$C(2,10)=2^3=8.$$
Next,
$$C(2,5)=C(1,5)+C(1,2).$$
Because \(5\ge 3\), we have \(C(1,5)=2^2=4\). Also
$$C(1,2)=C(0,2)+C(0,0)=2+1=3.$$
So \(C(2,5)=7\), and therefore \(C(3,10)=15\).
For the second branch, \(2<5\), so
$$C(3,2)=C(2,2)=C(1,2)=3.$$
Altogether,
$$S(10)=15+3=18.$$
Equivalently, \(15\) valid subsets avoid \(8\), while only \(3\) valid subsets use it: \(\{8\}\), \(\{8,1\}\), and \(\{8,2\}\).
The C++, Python, and Java implementations first generate all Fibonacci-like terms not exceeding \(N\), then compute their prefix sums. After that they evaluate the recurrence top-down.
Each recursive state is identified by two pieces of information: the largest index still available and the remaining limit. If no terms remain, the state returns \(1\). If the remaining limit covers the full prefix sum, the state returns \(2^{i+1}\) immediately. Otherwise the implementation adds the exclude branch and, when allowed, the include branch.
To avoid recomputing identical states, the implementation stores previously solved limits separately for each index in hash-based lookup tables. The final call uses the largest index with \(f_i\le N\) and the original bound \(N\).
Let \(k=m+1\) be the number of usable terms. Since \(f_i\) grows like \(\varphi^i\), we have \(k=\Theta(\log N)\).
If \(M\) denotes the number of distinct states \((i,L)\) actually visited, then both time and memory are \(O(M)\), because each state is computed once and then memoized. The recursion depth is \(O(k)=O(\log N)\).
A trivial upper bound is \(M=O(2^k)\), corresponding to the raw subset recursion, but the exact prefix-sum cutoff collapses many large branches immediately. That pruning is the reason the method is practical for the problem's input size.
Sei \(f_0=1\), \(f_1=2\) und \(f_{k+2}=f_{k+1}+f_k\). Zu einer Schranke \(N\) betrachten wir alle Terme \(f_i\le N\). Gesucht ist die Anzahl der Teilmengen dieser endlichen Fibonacci-artigen Menge, deren Summe höchstens \(N\) ist.
Ist \(m\) der größte Index mit \(f_m\le N\), dann lautet die Zielgröße
$$S(N)=\#\left\{B\subseteq \{f_0,f_1,\dots,f_m\}:\sum_{x\in B}x\le N\right\}.$$
Der Titel "Not Zeckendorf" weist darauf hin, dass hier nicht nur die eindeutige Darstellung mit nicht benachbarten Fibonacci-Zahlen gezählt wird. Jede Teilmenge ist erlaubt, daher können verschiedene Teilmengen dieselbe Summe liefern, etwa \(3\) und \(1+2\).
Die Implementierung zerlegt das Problem rekursiv und benutzt dabei eine exakte Abkürzung auf Basis von Präfixsummen.
Wegen der Rekurrenz \(f_{k+2}=f_{k+1}+f_k\) wächst die Folge exponentiell, also sind nur \(O(\log N)\) Terme relevant. Sobald der größte zulässige Index \(m\) feststeht, reduziert sich alles auf eine Teilmengen-Zählung über \(\{f_0,\dots,f_m\}\).
Das ist entscheidend: \(N\) selbst kann sehr groß sein, aber die Zahl der verfügbaren Folgenglieder bleibt klein genug für eine zustandsbasierte Rekursion.
Für \(-1\le i\le m\) und \(L\ge 0\) definieren wir
$$C(i,L)=\#\left\{B\subseteq \{f_0,f_1,\dots,f_i\}:\sum_{x\in B}x\le L\right\}.$$
Das bedeutet: Wie viele Teilmengen der ersten \(i+1\) Terme bleiben innerhalb des Budgets \(L\)? Die gesuchte Antwort ist
$$S(N)=C(m,N).$$
Als Basisfall gilt
$$C(-1,L)=1,$$
denn ohne verbleibende Terme existiert nur die leere Menge.
Jede zulässige Teilmenge von \(\{f_0,\dots,f_i\}\) enthält \(f_i\) entweder nicht oder doch.
Wird \(f_i\) nicht gewählt, erhält man \(C(i-1,L)\).
Wird \(f_i\) gewählt, muss der Rest in das kleinere Budget \(L-f_i\) passen. Das liefert \(C(i-1,L-f_i)\), aber nur falls \(L\ge f_i\).
Daraus folgt
$$C(i,L)= \begin{cases} C(i-1,L), & L<f_i,\\ C(i-1,L)+C(i-1,L-f_i), & L\ge f_i. \end{cases}$$
Genau diese Include-or-Exclude-Rekurrenz wird in allen drei Implementierungen ausgewertet.
Sei
$$P_i=\sum_{j=0}^{i} f_j.$$
Falls \(L\ge P_i\), dann passt sogar die Teilmenge mit allen verfügbaren Termen in das Limit \(L\). Also ist jede Teilmenge zulässig, und damit gilt exakt
$$C(i,L)=2^{i+1}\qquad\text{falls}\qquad L\ge P_i.$$
Das ist keine Näherung, sondern ein geschlossener Spezialfall, der komplette Rekursionszweige sofort beendet.
Für diese Folge erfüllen die Präfixsummen zusätzlich die Identität
$$P_i=f_{i+2}-2,$$
was sich induktiv aus derselben Rekurrenz ergibt. Die Implementierungen berechnen die Präfixsummen direkt und testen dann während der Rekursion auf diese Schranke.
Verschiedene Entscheidungswege können denselben Zustand \((i,L)\) erreichen. Wenn der größte noch verfügbare Index und das Restbudget feststehen, ist die vorherige Geschichte irrelevant. Der Zustandsraum ist daher ein gerichteter azyklischer Graph und kein Baum aus völlig unabhängigen Teilproblemen.
Memoisierung macht das exakt nutzbar: Jeder verschiedene Zustand \((i,L)\) wird einmal berechnet, gespeichert und bei späterem Wiederauftreten direkt wiederverwendet.
Die verwendbaren Terme sind
$$1,\ 2,\ 3,\ 5,\ 8,$$
also lauten die Präfixsummen
$$1,\ 3,\ 6,\ 11,\ 19.$$
Gesucht ist \(S(10)=C(4,10)\). Da \(10<19\), spalten wir nach \(8\) auf:
$$C(4,10)=C(3,10)+C(3,2).$$
Für den ersten Anteil gilt \(10<11\), also weiter nach \(5\):
$$C(3,10)=C(2,10)+C(2,5).$$
Weil \(10\ge 6\), ist
$$C(2,10)=2^3=8.$$
Weiter erhält man
$$C(2,5)=C(1,5)+C(1,2).$$
Da \(5\ge 3\), folgt \(C(1,5)=2^2=4\). Außerdem
$$C(1,2)=C(0,2)+C(0,0)=2+1=3.$$
Also ist \(C(2,5)=7\) und damit \(C(3,10)=15\).
Für den zweiten Zweig gilt \(2<5\), also
$$C(3,2)=C(2,2)=C(1,2)=3.$$
Somit insgesamt
$$S(10)=15+3=18.$$
Direkt interpretiert: \(15\) gültige Teilmengen vermeiden die \(8\), und genau \(3\) gültige Teilmengen benutzen sie, nämlich \(\{8\}\), \(\{8,1\}\) und \(\{8,2\}\).
Die C++-, Python- und Java-Implementierungen erzeugen zuerst alle Fibonacci-artigen Terme bis \(N\) und berechnen anschließend ihre Präfixsummen. Danach wird die Rekurrenz top-down ausgewertet.
Jeder rekursive Zustand wird durch zwei Angaben beschrieben: den größten noch verfügbaren Index und das verbleibende Limit. Wenn keine Terme mehr übrig sind, liefert der Zustand \(1\). Wenn das Restlimit die gesamte Präfixsumme abdeckt, gibt der Zustand sofort \(2^{i+1}\) zurück. Andernfalls addiert die Implementierung den Ausschluss-Zweig und, falls zulässig, den Einschluss-Zweig.
Damit identische Zustände nicht mehrfach berechnet werden, speichert die Implementierung für jeden Index bereits gelöste Restlimits in hashbasierten Tabellen. Der abschließende Aufruf verwendet den größten Index mit \(f_i\le N\) und die ursprüngliche Schranke \(N\).
Sei \(k=m+1\) die Zahl der verwendbaren Terme. Da \(f_i\) wie \(\varphi^i\) wächst, gilt \(k=\Theta(\log N)\).
Bezeichnet \(M\) die Zahl der tatsächlich besuchten Zustände \((i,L)\), dann betragen Laufzeit und Speicher jeweils \(O(M)\), weil jeder Zustand genau einmal berechnet und danach memoisiert wird. Die Rekursionstiefe ist \(O(k)=O(\log N)\).
Eine triviale obere Schranke ist \(M=O(2^k)\), entsprechend dem rohen Teilmengenbaum. In der Praxis bricht die exakte Präfixsummen-Regel jedoch viele große Teilbäume sofort ab, wodurch das Verfahren für die Aufgabenparameter schnell genug wird.
\(f_0=1\), \(f_1=2\) ve \(f_{k+2}=f_{k+1}+f_k\) olsun. Verilen bir \(N\) sınırı için \(f_i\le N\) olan tüm terimleri alıyoruz. Amaç, bu sonlu Fibonacci-benzeri kümenin toplamı en fazla \(N\) olan altkümelerini saymaktır.
\(f_m\le N\) koşulunu sağlayan en büyük indeks \(m\) ise aranan nicelik
$$S(N)=\#\left\{B\subseteq \{f_0,f_1,\dots,f_m\}:\sum_{x\in B}x\le N\right\}.$$
"Not Zeckendorf" başlığı, klasik Zeckendorf gösterimindeki gibi yalnızca ardışık olmayan Fibonacci terimlerini saymadığımızı hatırlatır. Burada her altküme serbesttir; dolayısıyla \(3\) ile \(1+2\) gibi farklı altkümeler aynı toplamı verebilir.
Uygulama, problemi özyinelemeli bir parçalama ve prefix toplamına dayanan tam bir budama kuralı ile çözer.
\(f_{k+2}=f_{k+1}+f_k\) bağıntısı nedeniyle dizi üstel hızla büyür; bu yüzden yalnızca \(O(\log N)\) kadar terim önemlidir. En büyük uygun indeks \(m\) bulunduktan sonra problem, \(\{f_0,\dots,f_m\}\) kümesi üzerinde bir altküme sayımına dönüşür.
Bu nokta kritiktir: \(N\) çok büyük olsa bile aday terim sayısı küçük kaldığı için durum tabanlı bir özyineleme uygulanabilir.
\(-1\le i\le m\) ve \(L\ge 0\) için
$$C(i,L)=\#\left\{B\subseteq \{f_0,f_1,\dots,f_i\}:\sum_{x\in B}x\le L\right\}$$
tanımını yapalım. Bu, ilk \(i+1\) terim içinden toplamı \(L\)'yi aşmayan kaç altküme olduğunu söyler. İstenen sonuç
$$S(N)=C(m,N)$$
olur. Taban durum ise
$$C(-1,L)=1$$
şeklindedir; çünkü hiç terim kalmadığında yalnızca boş küme vardır.
\(\{f_0,\dots,f_i\}\) içindeki her uygun altküme ya \(f_i\)'yi almaz ya da alır.
\(f_i\) alınmazsa katkı \(C(i-1,L)\) olur.
\(f_i\) alınırsa geri kalan terimler azaltılmış limit \(L-f_i\) içinde kalmalıdır. Bu da ancak \(L\ge f_i\) ise \(C(i-1,L-f_i)\) katkısı verir.
Dolayısıyla
$$C(i,L)= \begin{cases} C(i-1,L), & L<f_i,\\ C(i-1,L)+C(i-1,L-f_i), & L\ge f_i. \end{cases}$$
Üç dildeki uygulama tam olarak bu al veya alma özyinelemesini hesaplar.
Şunu tanımlayalım:
$$P_i=\sum_{j=0}^{i} f_j.$$
Eğer \(L\ge P_i\) ise, eldeki tüm terimlerin birlikte toplamı bile limiti aşmaz. Bu durumda her altküme geçerlidir ve
$$C(i,L)=2^{i+1}\qquad\text{koşuluyla}\qquad L\ge P_i$$
eşitliği doğrudur. Bu bir yaklaşım değil, tam bir kapalı form durumudur. Böylece özyinelemenin büyük bölümleri tek adımda kapanır.
Bu dizi için prefix toplamları ayrıca
$$P_i=f_{i+2}-2$$
özdeşliğini sağlar. Bu sonuç aynı Fibonacci-benzeri bağıntıdan tümevarımla çıkar. Uygulama kapalı formu kullanmak yerine prefix toplamlarını doğrudan hesaplayıp kesme testini recursion sırasında uygular.
Farklı seçim yolları aynı \((i,L)\) çiftine ulaşabilir. Bir durumda artık sadece en büyük kullanılabilir indeks ile kalan bütçe önemlidir; o noktaya hangi yoldan gelindiği önemli değildir. Bu yüzden durum uzayı bir ağaçtan çok yönlü çevrimsiz bir graf yapısındadır.
Memoization bunu doğrudan kullanır: Her farklı \((i,L)\) durumu bir kez çözülür, saklanır ve tekrar görüldüğünde hazır değeri geri döndürülür.
Kullanılan terimler
$$1,\ 2,\ 3,\ 5,\ 8$$
olur; prefix toplamları ise
$$1,\ 3,\ 6,\ 11,\ 19.$$
Aradığımız değer \(S(10)=C(4,10)\). \(10<19\) olduğundan önce \(8\)'e göre ayırırız:
$$C(4,10)=C(3,10)+C(3,2).$$
İlk terimde \(10<11\) olduğu için \(5\)'e göre tekrar ayırırız:
$$C(3,10)=C(2,10)+C(2,5).$$
\(10\ge 6\) olduğundan
$$C(2,10)=2^3=8.$$
Ayrıca
$$C(2,5)=C(1,5)+C(1,2).$$
\(5\ge 3\) olduğu için \(C(1,5)=2^2=4\). Diğer yandan
$$C(1,2)=C(0,2)+C(0,0)=2+1=3.$$
Böylece \(C(2,5)=7\) ve dolayısıyla \(C(3,10)=15\).
İkinci dalda \(2<5\) olduğu için
$$C(3,2)=C(2,2)=C(1,2)=3.$$
Sonuç olarak
$$S(10)=15+3=18.$$
Bunu doğrudan da okuyabiliriz: \(8\)'i almayan \(15\) geçerli altküme vardır; \(8\)'i alan geçerli altkümeler ise sadece \(\{8\}\), \(\{8,1\}\) ve \(\{8,2\}\) olmak üzere \(3\) tanedir.
C++, Python ve Java implementasyonları önce \(N\)'yi aşmayan Fibonacci-benzeri terimleri üretir, sonra bunların prefix toplamlarını hesaplar. Ardından özyinelemeli sayımı yukarıdan aşağıya çalıştırır.
Her durum iki bilgiyle belirlenir: elde kalan en büyük indeks ve kalan limit. Hiç terim kalmazsa durum \(1\) döndürür. Kalan limit tüm prefix toplamını kapsıyorsa durum doğrudan \(2^{i+1}\) döndürür. Aksi halde uygulama alma dalını ve izin varsa seçme dalını toplar.
Aynı durumların tekrar hesaplanmaması için her indeks için kalan limitlere göre hash tabanlı tablolar tutulur. Son çağrı, \(f_i\le N\) koşulunu sağlayan en büyük indeks ve başlangıç limiti \(N\) ile yapılır.
\(k=m+1\) kullanılabilir terim sayısı olsun. \(f_i\) yaklaşık \(\varphi^i\) hızında büyüdüğü için \(k=\Theta(\log N)\) olur.
Eğer \(M\), gerçekten ziyaret edilen farklı \((i,L)\) durumlarının sayısıysa, her durum bir kez hesaplanıp saklandığından zaman ve bellek maliyetleri \(O(M)\)'dir. Özyineleme derinliği de \(O(k)=O(\log N)\) olur.
Ham altküme ağacı için triviyal üst sınır \(M=O(2^k)\) olsa da, prefix toplamı kesmesi büyük dalları anında kapatır. Problemin gerçek giriş boyutunda yöntemi uygulanabilir kılan nokta budur.
Sea \(f_0=1\), \(f_1=2\) y \(f_{k+2}=f_{k+1}+f_k\). Para un límite dado \(N\), conservamos todos los términos \(f_i\le N\). Debemos contar cuántos subconjuntos de ese conjunto finito tipo Fibonacci tienen suma total menor o igual que \(N\).
Si \(m\) es el mayor índice con \(f_m\le N\), entonces la cantidad buscada es
$$S(N)=\#\left\{B\subseteq \{f_0,f_1,\dots,f_m\}:\sum_{x\in B}x\le N\right\}.$$
El título "Not Zeckendorf" recuerda que aquí no exigimos la representación única con términos no consecutivos. Se permite cualquier subconjunto, así que distintos subconjuntos pueden producir la misma suma, por ejemplo \(3\) y \(1+2\).
La implementación resuelve el conteo mediante descomposición recursiva y una poda exacta basada en sumas prefijo.
La recurrencia \(f_{k+2}=f_{k+1}+f_k\) hace que la sucesión crezca de forma exponencial, de modo que solo hay \(O(\log N)\) términos relevantes. Una vez hallado el mayor índice utilizable \(m\), todo se reduce a contar subconjuntos de \(\{f_0,\dots,f_m\}\).
Esto es importante porque \(N\) puede ser enorme, pero el número de términos candidatos sigue siendo lo bastante pequeño como para trabajar con estados recursivos.
Para \(-1\le i\le m\) y \(L\ge 0\), definimos
$$C(i,L)=\#\left\{B\subseteq \{f_0,f_1,\dots,f_i\}:\sum_{x\in B}x\le L\right\}.$$
Es decir, entre los primeros \(i+1\) términos, cuántos subconjuntos permanecen dentro del presupuesto \(L\). La respuesta final es
$$S(N)=C(m,N).$$
El caso base es
$$C(-1,L)=1,$$
porque si ya no quedan términos, solo sobrevive el subconjunto vacío.
Cada subconjunto admisible de \(\{f_0,\dots,f_i\}\) o bien excluye \(f_i\) o bien lo incluye.
Si no se elige \(f_i\), la contribución es \(C(i-1,L)\).
Si se elige \(f_i\), el resto debe caber en el límite reducido \(L-f_i\), lo que aporta \(C(i-1,L-f_i)\), pero solo cuando \(L\ge f_i\).
Por tanto,
$$C(i,L)= \begin{cases} C(i-1,L), & L<f_i,\\ C(i-1,L)+C(i-1,L-f_i), & L\ge f_i. \end{cases}$$
Esta es exactamente la recurrencia de incluir o excluir que evalúan las tres implementaciones.
Definimos
$$P_i=\sum_{j=0}^{i} f_j.$$
Si \(L\ge P_i\), entonces incluso el subconjunto que contiene todos los términos disponibles tiene suma menor o igual que \(L\). En consecuencia, todos los subconjuntos son válidos y obtenemos la fórmula cerrada
$$C(i,L)=2^{i+1}\qquad\text{cuando}\qquad L\ge P_i.$$
Este atajo es exacto y elimina subárboles completos de la recursión.
Para esta sucesión además se cumple
$$P_i=f_{i+2}-2,$$
identidad que se demuestra por inducción usando la misma recurrencia. Las implementaciones calculan las sumas prefijo directamente y luego aplican este criterio durante la búsqueda recursiva.
Distintos caminos de decisión pueden llegar al mismo par \((i,L)\). Una vez fijados el mayor índice disponible y el presupuesto restante, la historia anterior deja de importar. Por eso el espacio de estados es un grafo acíclico dirigido y no un árbol de problemas independientes.
La memoización aprovecha exactamente esa estructura: cada estado distinto \((i,L)\) se resuelve una vez, se guarda y se reutiliza cuando vuelve a aparecer.
Los términos utilizables son
$$1,\ 2,\ 3,\ 5,\ 8,$$
y sus sumas prefijo son
$$1,\ 3,\ 6,\ 11,\ 19.$$
Queremos \(S(10)=C(4,10)\). Como \(10<19\), separamos según \(8\):
$$C(4,10)=C(3,10)+C(3,2).$$
En la primera parte, \(10<11\), así que volvemos a separar según \(5\):
$$C(3,10)=C(2,10)+C(2,5).$$
Ahora \(10\ge 6\), luego
$$C(2,10)=2^3=8.$$
Además,
$$C(2,5)=C(1,5)+C(1,2).$$
Como \(5\ge 3\), se obtiene \(C(1,5)=2^2=4\). Y
$$C(1,2)=C(0,2)+C(0,0)=2+1=3.$$
Por tanto \(C(2,5)=7\), y entonces \(C(3,10)=15\).
En la segunda rama, \(2<5\), de modo que
$$C(3,2)=C(2,2)=C(1,2)=3.$$
Finalmente,
$$S(10)=15+3=18.$$
La lectura combinatoria es la misma: \(15\) subconjuntos válidos no usan \(8\), y solo \(3\) lo usan, a saber \(\{8\}\), \(\{8,1\}\) y \(\{8,2\}\).
Las implementaciones en C++, Python y Java primero generan todos los términos tipo Fibonacci que no superan \(N\) y luego calculan sus sumas prefijo. Después evalúan la recurrencia de arriba hacia abajo.
Cada estado recursivo queda determinado por dos datos: el mayor índice aún disponible y el límite restante. Si ya no quedan términos, el estado devuelve \(1\). Si el límite restante cubre toda la suma prefijo, el estado devuelve inmediatamente \(2^{i+1}\). En caso contrario, la implementación suma la rama que excluye el término actual y, si es posible, la rama que lo incluye.
Para evitar recomputaciones, la implementación guarda los límites ya resueltos por separado para cada índice en tablas hash. La llamada final usa el mayor índice con \(f_i\le N\) y el límite original \(N\).
Sea \(k=m+1\) el número de términos utilizables. Como \(f_i\) crece como \(\varphi^i\), se tiene \(k=\Theta(\log N)\).
Si \(M\) es el número de estados distintos \((i,L)\) realmente visitados, entonces el tiempo y la memoria son \(O(M)\), porque cada estado se calcula una sola vez y después queda memoizado. La profundidad de la recursión es \(O(k)=O(\log N)\).
Una cota superior trivial es \(M=O(2^k)\), la del árbol bruto de subconjuntos, pero el corte exacto por suma prefijo elimina muchas ramas grandes de inmediato. Por eso el metodo resulta practico para el tamaño real de la entrada.
设 \(f_0=1\)、\(f_1=2\)，并满足递推式 \(f_{k+2}=f_{k+1}+f_k\)。给定上界 \(N\)，我们保留所有满足 \(f_i\le N\) 的项。题目要求统计：这个有限的 Fibonacci 型集合有多少个子集，其元素和不超过 \(N\)。
如果 \(m\) 是满足 \(f_m\le N\) 的最大下标，那么目标可以写成
$$S(N)=\#\left\{B\subseteq \{f_0,f_1,\dots,f_m\}:\sum_{x\in B}x\le N\right\}.$$
题目名中的 "Not Zeckendorf" 表示这里并不是在统计标准的 Zeckendorf 表示。标准结论要求使用互不相邻的 Fibonacci 项并且表示唯一，而这里没有这种限制，任何子集都允许，因此不同子集可能得到同一个和，例如 \(3\) 与 \(1+2\)。
实现采用的是精确递归计数，再配合一个由前缀和触发的精确剪枝规则。
由于 \(f_{k+2}=f_{k+1}+f_k\) 使得数列按指数级增长，所以不超过 \(N\) 的项只有 \(O(\log N)\) 个。一旦找出最大可用下标 \(m\)，原问题就转化为在集合 \(\{f_0,\dots,f_m\}\) 上做子集计数。
这一点非常关键。虽然 \(N\) 本身可以大到 \(10^{13}\) 级别，但真正需要考虑的候选数并不多，因此可以用状态化递归来精确求解。
对 \(-1\le i\le m\) 且 \(L\ge 0\)，定义
$$C(i,L)=\#\left\{B\subseteq \{f_0,f_1,\dots,f_i\}:\sum_{x\in B}x\le L\right\}.$$
它表示：只看前 \(i+1\) 个数时，总和不超过预算 \(L\) 的子集有多少个。原题所求正是
$$S(N)=C(m,N).$$
空集约定给出边界条件
$$C(-1,L)=1,$$
因为当没有任何可选项时，唯一的子集就是空集。
对集合 \(\{f_0,\dots,f_i\}\) 中的任意合法子集，关于 \(f_i\) 只有两种可能：不选它，或者选它。
如果不选 \(f_i\)，贡献就是 \(C(i-1,L)\)。
如果选 \(f_i\)，那么其余元素的总和必须不超过缩小后的预算 \(L-f_i\)，对应贡献为 \(C(i-1,L-f_i)\)，但这只有在 \(L\ge f_i\) 时才有意义。
因此得到精确递推
$$C(i,L)= \begin{cases} C(i-1,L), & L<f_i,\\ C(i-1,L)+C(i-1,L-f_i), & L\ge f_i. \end{cases}$$
这就是 C++、Python 和 Java 实现共同计算的核心递推式。
定义前缀和
$$P_i=\sum_{j=0}^{i} f_j.$$
如果 \(L\ge P_i\)，那么把前 \(i+1\) 个数全部选上，总和也不会超过 \(L\)。既然最大可能和都合法，所有子集自然都合法，所以直接得到闭式
$$C(i,L)=2^{i+1}\qquad\text{当}\qquad L\ge P_i.$$
这不是经验性剪枝，而是完全精确的数学结论。它可以把整棵递归子树直接折叠成一个幂值。
对这条具体数列，还可以推出
$$P_i=f_{i+2}-2.$$
这个恒等式可由归纳法证明：假设 \(P_{i-1}=f_{i+1}-2\)，则
$$P_i=P_{i-1}+f_i=(f_{i+1}-2)+f_i=f_{i+2}-2.$$
程序并没有依赖这个闭式，而是直接把前缀和预先算出来，然后在递归时检查是否满足 cutoff 条件。
不同的选取路径有可能走到同一个状态 \((i,L)\)。一旦当前最大可用下标和剩余预算确定，之前是通过什么路径到达这里已经不重要了。也就是说，状态空间本质上是一个有向无环图，而不是每条路径都互不相交的树。
因此记忆化是完全精确的优化：每个不同的 \((i,L)\) 只求一次，存起来之后，后续再次遇到同一状态时直接返回缓存结果。
不超过 \(10\) 的可用项是
$$1,\ 2,\ 3,\ 5,\ 8,$$
对应前缀和为
$$1,\ 3,\ 6,\ 11,\ 19.$$
目标是 \(S(10)=C(4,10)\)。因为 \(10<19\)，先按是否选 \(8\) 划分：
$$C(4,10)=C(3,10)+C(3,2).$$
第一项里有 \(10<11\)，所以继续按 \(5\) 划分：
$$C(3,10)=C(2,10)+C(2,5).$$
现在 \(10\ge 6\)，说明前三项 \(1,2,3\) 的所有子集都合法，因此
$$C(2,10)=2^3=8.$$
接着
$$C(2,5)=C(1,5)+C(1,2).$$
由于 \(5\ge 3\)，前两项 \(1,2\) 的所有子集都可以选，所以
$$C(1,5)=2^2=4.$$
而
$$C(1,2)=C(0,2)+C(0,0)=2+1=3.$$
于是 \(C(2,5)=7\)，从而 \(C(3,10)=15\)。
再看第二个分支，由于 \(2<5\)，不可能再选 \(5\)，因此
$$C(3,2)=C(2,2)=C(1,2)=3.$$
最终得到
$$S(10)=15+3=18.$$
从组合意义上看也很直观：不含 \(8\) 的合法子集有 \(15\) 个；含 \(8\) 的合法子集只有 \(3\) 个，分别是 \(\{8\}\)、\(\{8,1\}\)、\(\{8,2\}\)。
C++、Python 和 Java 实现都先生成不超过 \(N\) 的 Fibonacci 型数列项，再顺序计算这些项的前缀和。随后，它们用自顶向下的方式求解上面的递推。
每个递归状态只由两部分信息决定：当前还能使用到哪个最大下标，以及剩余预算是多少。若已经没有可选项，则返回 \(1\)。若剩余预算至少覆盖当前前缀和，则直接返回 \(2^{i+1}\)。否则，程序先计算“不选当前项”的分支，再在预算允许时加上“选当前项”的分支。
为了避免重复计算，实现为每个下标分别维护基于哈希的缓存表，键是剩余预算，值是该状态的计数结果。最终调用使用的是满足 \(f_i\le N\) 的最大下标以及原始预算 \(N\)。
设可用项个数为 \(k=m+1\)。由于 \(f_i\) 按 \(\varphi^i\) 增长，所以 \(k=\Theta(\log N)\)。
若 \(M\) 表示实际访问到的不同状态 \((i,L)\) 数量，那么时间复杂度和空间复杂度都是 \(O(M)\)，因为每个状态只会被求值一次并缓存下来。递归深度为 \(O(k)=O(\log N)\)。
一个平凡上界是 \(M=O(2^k)\)，这对应未经优化的子集递归树。但前缀和 cutoff 能立即折叠大量大分支，因此真实运行量远小于朴素枚举，这也是该方法能够处理题目规模的原因。
Пусть \(f_0=1\), \(f_1=2\), а \(f_{k+2}=f_{k+1}+f_k\). Для заданной границы \(N\) берутся все члены этой Fibonacci-подобной последовательности, не превосходящие \(N\). Нужно посчитать, сколько подмножеств этого конечного набора имеют сумму не больше \(N\).
Если \(m\) - наибольший индекс, для которого \(f_m\le N\), то искомая величина равна
$$S(N)=\#\left\{B\subseteq \{f_0,f_1,\dots,f_m\}:\sum_{x\in B}x\le N\right\}.$$
Название "Not Zeckendorf" подчеркивает, что здесь не требуется единственное представление числа через непоследовательные Fibonacci-термы. Разрешено любое подмножество, поэтому разные подмножества могут давать одну и ту же сумму, например \(3\) и \(1+2\).
Решение основано на точном рекурсивном разбиении и на точном отсечении по префиксной сумме.
Из-за рекуррентного соотношения \(f_{k+2}=f_{k+1}+f_k\) последовательность растет экспоненциально, поэтому полезных членов всего \(O(\log N)\). После нахождения максимального допустимого индекса \(m\) задача сводится к подсчету подмножеств множества \(\{f_0,\dots,f_m\}\).
Это ключевой переход: само число \(N\) может быть очень большим, но количество рассматриваемых элементов остается достаточно малым для рекурсивного перебора по состояниям.
Для \(-1\le i\le m\) и \(L\ge 0\) определим
$$C(i,L)=\#\left\{B\subseteq \{f_0,f_1,\dots,f_i\}:\sum_{x\in B}x\le L\right\}.$$
Это число подмножеств первых \(i+1\) элементов, сумма которых не превышает \(L\). Тогда ответ задачи равен
$$S(N)=C(m,N).$$
Базовый случай имеет вид
$$C(-1,L)=1,$$
потому что при отсутствии доступных элементов остается только пустое подмножество.
Любое допустимое подмножество множества \(\{f_0,\dots,f_i\}\) либо не содержит \(f_i\), либо содержит его.
В первом случае вклад равен \(C(i-1,L)\).
Во втором случае оставшиеся элементы должны укладываться в уменьшенный лимит \(L-f_i\), что дает вклад \(C(i-1,L-f_i)\), но только когда \(L\ge f_i\).
Следовательно,
$$C(i,L)= \begin{cases} C(i-1,L), & L<f_i,\\ C(i-1,L)+C(i-1,L-f_i), & L\ge f_i. \end{cases}$$
Именно эту точную рекурсию выбора или пропуска текущего элемента используют реализации на C++, Python и Java.
Обозначим
$$P_i=\sum_{j=0}^{i} f_j.$$
Если \(L\ge P_i\), то даже подмножество, содержащее все доступные элементы, имеет сумму не больше \(L\). Значит, допустимы вообще все подмножества, и потому
$$C(i,L)=2^{i+1}\qquad\text{при}\qquad L\ge P_i.$$
Это не эвристика, а точное замыкание большой рекурсивной ветви в одну формулу.
Для данной последовательности дополнительно выполняется
$$P_i=f_{i+2}-2,$$
что легко доказывается индукцией из той же рекуррентной формулы. В реализации префиксные суммы вычисляются напрямую, а затем во время рекурсии проверяется условие cutoff.
Разные последовательности решений могут приводить к одному и тому же состоянию \((i,L)\). Как только известны максимальный доступный индекс и оставшийся лимит, предыстория уже не имеет значения. Поэтому пространство состояний представляет собой ориентированный ациклический граф, а не дерево полностью независимых ветвей.
Мемоизация использует это наблюдение буквально: каждое состояние \((i,L)\) вычисляется один раз, сохраняется и затем мгновенно переиспользуется при повторном появлении.
Подходящие элементы:
$$1,\ 2,\ 3,\ 5,\ 8,$$
а их префиксные суммы равны
$$1,\ 3,\ 6,\ 11,\ 19.$$
Нужно найти \(S(10)=C(4,10)\). Поскольку \(10<19\), сначала разбиваем по числу \(8\):
$$C(4,10)=C(3,10)+C(3,2).$$
В первой части имеем \(10<11\), поэтому еще раз разбиваем по числу \(5\):
$$C(3,10)=C(2,10)+C(2,5).$$
Так как \(10\ge 6\), получаем
$$C(2,10)=2^3=8.$$
Далее,
$$C(2,5)=C(1,5)+C(1,2).$$
Поскольку \(5\ge 3\), имеем \(C(1,5)=2^2=4\). Кроме того,
$$C(1,2)=C(0,2)+C(0,0)=2+1=3.$$
Значит, \(C(2,5)=7\), а потому \(C(3,10)=15\).
Во второй ветви \(2<5\), следовательно
$$C(3,2)=C(2,2)=C(1,2)=3.$$
Итак,
$$S(10)=15+3=18.$$
Комбинаторная интерпретация та же: \(15\) допустимых подмножеств не используют \(8\), а только \(3\) допустимых подмножества используют его, а именно \(\{8\}\), \(\{8,1\}\) и \(\{8,2\}\).
Реализации на C++, Python и Java сначала строят все Fibonacci-подобные элементы, не превосходящие \(N\), а затем вычисляют их префиксные суммы. После этого рекуррентная формула вычисляется сверху вниз.
Каждое рекурсивное состояние задается двумя параметрами: максимальным еще доступным индексом и оставшимся лимитом. Если элементов больше нет, состояние возвращает \(1\). Если оставшийся лимит покрывает всю текущую префиксную сумму, состояние немедленно возвращает \(2^{i+1}\). В противном случае реализация суммирует ветвь без текущего элемента и, если позволяет бюджет, ветвь с текущим элементом.
Чтобы не пересчитывать одинаковые состояния, для каждого индекса хранится отдельная хеш-таблица уже решенных значений лимита. Финальный вызов использует максимальный индекс с условием \(f_i\le N\) и исходную границу \(N\).
Пусть \(k=m+1\) - число доступных элементов. Поскольку \(f_i\) растет как \(\varphi^i\), имеем \(k=\Theta(\log N)\).
Если \(M\) обозначает количество различных реально посещенных состояний \((i,L)\), то и время, и память равны \(O(M)\), потому что каждое состояние вычисляется один раз и затем мемоизируется. Глубина рекурсии равна \(O(k)=O(\log N)\).
Тривиальная верхняя оценка \(M=O(2^k)\) соответствует сырому дереву подмножеств, но точное отсечение по префиксной сумме мгновенно схлопывает многие большие ветви. Именно это делает метод практичным для реального размера входа.
لتكن \(f_0=1\) و\(f_1=2\) وتحقق المتتالية العلاقة \(f_{k+2}=f_{k+1}+f_k\). عند حد معطى \(N\)، نأخذ كل حد يحقق \(f_i\le N\). المطلوب هو عد عدد المجموعات الجزئية من هذه المجموعة المحدودة ذات الطابع الفيبوناتشي التي لا يتجاوز مجموع عناصرها \(N\).
إذا كان \(m\) هو أكبر فهرس يحقق \(f_m\le N\)، فإن الكمية المطلوبة هي
$$S(N)=\#\left\{B\subseteq \{f_0,f_1,\dots,f_m\}:\sum_{x\in B}x\le N\right\}.$$
اسم المسألة "Not Zeckendorf" يعني أننا لا نبحث عن التمثيل الفريد باستخدام حدود فيبوناتشي غير المتجاورة فقط. هنا كل مجموعة جزئية مسموحة، ولذلك قد تعطي مجموعتان مختلفتان المجموع نفسه، مثل \(3\) و\(1+2\).
الحل يعتمد على تفكيك عودي دقيق مع قاعدة تقليم دقيقة مبنية على المجاميع البادئة.
بما أن العلاقة \(f_{k+2}=f_{k+1}+f_k\) تجعل المتتالية تنمو أسيًا، فإن عدد الحدود التي لا تتجاوز \(N\) هو فقط \(O(\log N)\). بعد تحديد أكبر فهرس صالح \(m\)، تصبح المسألة مجرد عد للمجموعات الجزئية داخل \(\{f_0,\dots,f_m\}\).
هذه الملاحظة أساسية، لأن \(N\) قد يكون ضخمًا جدًا بينما يبقى عدد الحدود المرشحة صغيرًا بما يكفي لتطبيق عودية مبنية على الحالات.
لكل \(-1\le i\le m\) ولكل \(L\ge 0\)، نعرف
$$C(i,L)=\#\left\{B\subseteq \{f_0,f_1,\dots,f_i\}:\sum_{x\in B}x\le L\right\}.$$
أي: من بين أول \(i+1\) حدود، كم مجموعة جزئية يبقى مجموعها ضمن الميزانية \(L\)؟ عندئذ يكون الجواب النهائي
$$S(N)=C(m,N).$$
وحالة الأساس هي
$$C(-1,L)=1,$$
لأنه عندما لا يبقى أي عنصر للاختيار، لا تبقى إلا المجموعة الخالية.
كل مجموعة جزئية مقبولة من \(\{f_0,\dots,f_i\}\) إما أن تستبعد \(f_i\) أو أن تضمّه.
إذا استبعدنا \(f_i\)، فالمساهمة هي \(C(i-1,L)\).
وإذا ضممنا \(f_i\)، فيجب أن تقع بقية العناصر ضمن الحد الأصغر \(L-f_i\)، وهذا يعطي \(C(i-1,L-f_i)\)، لكن فقط عندما \(L\ge f_i\).
إذًا نحصل على العلاقة الدقيقة
$$C(i,L)= \begin{cases} C(i-1,L), & L<f_i,\\ C(i-1,L)+C(i-1,L-f_i), & L\ge f_i. \end{cases}$$
وهذه بالضبط هي علاقة الاختيار أو عدم الاختيار التي تنفذها التطبيقات الثلاثة.
نعرف
$$P_i=\sum_{j=0}^{i} f_j.$$
إذا كان \(L\ge P_i\)، فهذا يعني أن حتى المجموعة التي تحتوي كل الحدود المتاحة يبقى مجموعها ضمن \(L\). وبالتالي تصبح كل المجموعات الجزئية صالحة، فنحصل على الصيغة المغلقة
$$C(i,L)=2^{i+1}.$$
ويحدث ذلك عندما يكون \(L\ge P_i\).
هذا ليس تقريبًا، بل حالة دقيقة تمامًا تختصر فروعًا كبيرة من الشجرة العودية في خطوة واحدة.
ولهذه المتتالية تحديدًا نجد أيضًا
$$P_i=f_{i+2}-2.$$
وتثبت هذه الهوية بالاستقراء من العلاقة نفسها. أما التنفيذ فيحسب المجاميع البادئة مباشرة ثم يختبر شرط القطع أثناء العودية.
قد تصل مسارات قرار مختلفة إلى الحالة نفسها \((i,L)\). وبمجرد أن نعرف أكبر فهرس ما زال متاحًا والميزانية المتبقية، لا تعود طريقة الوصول إلى هذه الحالة مهمة. لذلك فإن فضاء الحالات هو رسم بياني موجه لا دوري، وليس شجرة من مسائل مستقلة تمامًا.
من هنا تأتي فائدة الحفظية: كل حالة مختلفة \((i,L)\) تحسب مرة واحدة فقط، ثم تخزن، وأي ظهور لاحق لها يعاد منه الجواب مباشرة.
الحدود القابلة للاستخدام هي
$$1,\ 2,\ 3,\ 5,\ 8,$$
ومجاميعها البادئة هي
$$1,\ 3,\ 6,\ 11,\ 19.$$
نريد \(S(10)=C(4,10)\). وبما أن \(10<19\)، نقسم بحسب العدد \(8\):
$$C(4,10)=C(3,10)+C(3,2).$$
في الفرع الأول لدينا \(10<11\)، لذلك نقسم مرة أخرى بحسب \(5\):
$$C(3,10)=C(2,10)+C(2,5).$$
ولأن \(10\ge 6\)، فإن كل المجموعات الجزئية للحدود \(1,2,3\) صالحة، وبالتالي
$$C(2,10)=2^3=8.$$
ثم
$$C(2,5)=C(1,5)+C(1,2).$$
وبما أن \(5\ge 3\)، نحصل على \(C(1,5)=2^2=4\). كذلك
$$C(1,2)=C(0,2)+C(0,0)=2+1=3.$$
إذن \(C(2,5)=7\)، ومن ثم \(C(3,10)=15\).
أما في الفرع الثاني فلدينا \(2<5\)، لذلك
$$C(3,2)=C(2,2)=C(1,2)=3.$$
وعليه
$$S(10)=15+3=18.$$
ويمكن تفسير ذلك مباشرة: توجد \(15\) مجموعة جزئية صالحة لا تستخدم \(8\)، بينما توجد فقط \(3\) مجموعات صالحة تستخدمه، وهي \(\{8\}\) و\(\{8,1\}\) و\(\{8,2\}\).
تبدأ تطبيقات C++ وPython وJava بتوليد جميع الحدود ذات الطابع الفيبوناتشي التي لا تتجاوز \(N\)، ثم تحسب المجاميع البادئة لها. بعد ذلك تنفذ العلاقة العودية من الأعلى إلى الأسفل.
كل حالة عودية يحددها أمران فقط: أكبر فهرس ما زال متاحًا، والحد المتبقي. إذا لم يبق أي حد، تعيد الحالة القيمة \(1\). وإذا كان الحد المتبقي يغطي كامل المجموع البادئ الحالي، تعيد الحالة مباشرة \(2^{i+1}\). وإلا فإن التنفيذ يجمع فرع الاستبعاد، ويضيف فرع الاختيار عندما تسمح الميزانية بذلك.
ولتجنب إعادة الحساب، تحتفظ التطبيقات بجدول تجزئة منفصل لكل فهرس، مفاتيحه هي الحدود المتبقية التي سبق حلها. أما النداء النهائي فيستخدم أكبر فهرس يحقق \(f_i\le N\) مع الحد الأصلي \(N\).
ليكن \(k=m+1\) هو عدد الحدود القابلة للاستخدام. وبما أن \(f_i\) ينمو مثل \(\varphi^i\)، فإن \(k=\Theta(\log N)\).
إذا رمزنا بعدد الحالات المختلفة المزارة فعليًا بالرمز \(M\)، فإن الزمن والذاكرة كلاهما يساويان \(O(M)\)، لأن كل حالة تحسب مرة واحدة فقط ثم تحفظ. كما أن عمق العودية يساوي \(O(k)=O(\log N)\).
يوجد حد أعلى بسيط \(M=O(2^k)\) يوافق شجرة المجموعات الجزئية الخام، لكن شرط القطع بالمجموع البادئ يختصر فروعًا كبيرة فورًا. وهذا هو السبب في أن الطريقة عملية عند حجم الإدخال الحقيقي للمسألة.