Detailed mathematical approach

Problem Summary

The problem asks for the number of unordered decompositions of \(100\) into at least two positive integers. In partition language, we want every partition of \(100\) except the single-part partition \(100\) itself.

Equivalently, we may count partitions of \(100\) whose largest part is at most \(99\). That quantity is \(p(100)-1=190{,}569{,}291\), and the implementations compute it directly without ever generating the partitions themselves.

Mathematical Approach

The natural state for this problem is a restricted partition count. Instead of asking for all partitions at once, we count how many ways a sum can be formed when only small parts are allowed.

Restricted Partitions and the Right State Space

For integers \(s \ge 0\) and \(k \ge 0\), let \(P_k(s)\) be the number of partitions of \(s\) using only parts from the set \(\{1,2,\dots,k\}\). The Project Euler question for a general target \(n\) is therefore

$P_{n-1}(n).$

The upper limit is \(n-1\), not \(n\), because allowing the part \(n\) would introduce the trivial one-term partition \(n\), which the problem excludes.

This point of view also matches the generating function

$\sum_{s\ge 0} P_k(s)x^s=\prod_{j=1}^{k}\frac{1}{1-x^j}.$

For Problem 76 we need the coefficient of \(x^{100}\) in \(\prod_{j=1}^{99}(1-x^j)^{-1}\). Each factor expands as \(1+x^j+x^{2j}+\cdots\), so choosing a term from every factor records how many copies of each allowed part are used.

Splitting Partitions by Whether They Use the Current Part

Fix \(k \ge 1\). Every partition counted by \(P_k(s)\) falls into exactly one of two disjoint classes:

Partitions that do not use the part \(k\), counted by \(P_{k-1}(s)\).

Partitions that use at least one \(k\). Removing one copy of \(k\) leaves a partition of \(s-k\) whose parts are still at most \(k\), counted by \(P_k(s-k)\).

That gives the recurrence

$P_k(s)=P_{k-1}(s)+P_k(s-k)\qquad (s\ge k).$

The boundary conditions are just as important:

$P_k(0)=1 \quad \text{for all } k\ge 0,\qquad P_0(s)=0 \quad \text{for all } s\gt 0.$

The first identity says that there is exactly one way to form zero, namely the empty partition. The second says that no positive sum can be formed when no positive parts are available.

Why the One-Dimensional Dynamic Program Is Correct

The implementations compress the recurrence into one array. After finishing the outer-loop step for a particular part \(k\), the entry at position \(s\) stores exactly \(P_k(s)\).

The update rule is

$\text{ways}[s]\leftarrow \text{ways}[s]+\text{ways}[s-k]\qquad (s=k,k+1,\dots,n).$

Before processing part \(k\), the cell \(\text{ways}[s]\) holds \(P_{k-1}(s)\). Because the inner loop runs upward, the cell \(\text{ways}[s-k]\) has already been updated for the same \(k\), so it holds \(P_k(s-k)\). One in-place addition therefore realizes the recurrence above.

This upward sweep is the key invariant of the whole method. It allows the current part \(k\) to be used repeatedly. If the sweep ran downward, each part would be used at most once, which would solve a different problem.

Worked Example: Target \(5\)

For \(n=5\), excluding the trivial partition \(5\), the valid decompositions are

$4+1,\quad 3+2,\quad 3+1+1,\quad 2+2+1,\quad 2+1+1+1,\quad 1+1+1+1+1.$

So the correct answer is \(6\). The array states make the recurrence visible:

After allowing only part \(1\): \([1,1,1,1,1,1]\).

After also allowing part \(2\): \([1,1,2,2,3,3]\).

After also allowing part \(3\): \([1,1,2,3,4,5]\).

After also allowing part \(4\): \([1,1,2,3,5,6]\).

The final value is \(\text{ways}[5]=6\), exactly matching the checkpoint used by the implementations.

How the Code Works

Initialization

The array is created with \(\text{ways}[0]=1\) and every other entry equal to \(0\). That single nonzero value encodes the base fact \(P_k(0)=1\).

The Nested Loops

The outer loop runs through candidate parts \(1,2,\dots,n-1\). Stopping at \(n-1\) is mathematically deliberate: it removes the one-part decomposition \(n\) from the count. For each part, the inner loop visits all sums from that part up to \(n\) and performs one in-place addition.

Because the inner loop is increasing, the current part may be reused any number of times. That is exactly what partitions require, and it is the reason the one-dimensional array produces unrestricted multiplicities instead of a subset-sum style count.

Language-Level Differences

The C++, Python, and Java implementations all use the same recurrence and the same update order. The C++ and Python versions expose a configurable target \(n\) and also verify the sample case \(n=5\rightarrow 6\) before printing the main answer. The Java version keeps the Project Euler value \(n=100\) directly in a shorter fixed-size program.

After the loops finish, the output cell is \(\text{ways}[n]=P_{n-1}(n)\). For Problem 76 this is \(190{,}569{,}291\).

Complexity Analysis

For each part \(k\in\{1,\dots,n-1\}\), the inner loop performs \(n-k+1\) updates. The exact number of additions is therefore

$\sum_{k=1}^{n-1}(n-k+1)=\frac{(n-1)(n+2)}{2}.$

That is \(O(n^2)\) time and \(O(n)\) space. When \(n=100\), the program performs exactly \(5049\) in-place additions, so the computation is tiny compared with the size of the answer.

Footnotes and References

1. Problem page: Project Euler 76 - Counting Summations
2. Integer partitions: Wikipedia - Partition (number theory)
3. Generating functions: Wikipedia - Generating function
4. Coin-change viewpoint: Wikipedia - Change-making problem