Solution

Answer: 73682

To solve this problem, we must count the number of distinct unordered combinations of British coins that sum to 200 pence.

The available coin denominations are:

$$1,2,5,10,20,50,100,200$$

We want the number of nonnegative integer solutions to

$$1a+2b+5c+10d+20e+50f+100g+200h=200$$

where each variable represents how many of that coin are used.

Mathematical analysis

This is a classic integer partition / coin change problem.

The key insight is:

Order does not matter.
We count combinations, not permutations.

For example:

$1p + 2p + 2p$
$2p + 1p + 2p$

are the same combination.

A brute-force permutation search would massively overcount.

Dynamic programming approach

Define:

$$dp[n]$$

to mean:

the number of ways to form $n$ pence using the coins processed so far.

Initially:

$$dp[0]=1$$

because there is exactly one way to make 0p: use no coins.

All other values start at 0.

Transition rule

Suppose we process coins one at a time.

For a coin value $c$, every amount $n \ge c$ can be formed by:

taking one coin $c$,
plus any valid way to form $n-c$.

Therefore:

$$dp[n] \leftarrow dp[n] + dp[n-c]$$

Processing coins in increasing order guarantees combinations are counted exactly once.

Why this avoids overcounting

Consider forming 7p.

If we process:

1p coins,
then 2p coins,
then 5p coins,

then every combination is generated in a canonical order.

For example:

$$5+2$$

is counted when processing the 5p coin.

But:

$$2+5$$

is not separately generated later, because the algorithm never revisits smaller coin types afterward.

Thus each unordered combination appears exactly once.

Python implementation

# Coin denominations in pence
coins = [1, 2, 5, 10, 20, 50, 100, 200]

# Target amount (£2 = 200p)
target = 200

# dp[n] = number of ways to make n pence
dp = [0] * (target + 1)

# Base case:
# There is exactly one way to make 0p
dp[0] = 1

# Process each coin
for coin in coins:
    # Update all reachable amounts
    for amount in range(coin, target + 1):
        dp[amount] += dp[amount - coin]

# Final answer
print(dp[target])

Code walkthrough

1. Coin list

coins = [1, 2, 5, 10, 20, 50, 100, 200]

These are the legal UK coin denominations.

2. Target amount

target = 200

We seek the number of ways to make 200p.

3. DP array

dp = [0] * (target + 1)

Creates entries:

$$dp[0], dp[1], \dots, dp[200]$$

Initially all are zero.

4. Base case

dp[0] = 1

There is one way to make 0p:

choose no coins.

This seed value propagates all future counts.

5. Main recurrence

for coin in coins:

Process coins one denomination at a time.

Inner loop

for amount in range(coin, target + 1):

For every amount that can include this coin.

Transition

dp[amount] += dp[amount - coin]

Every way to make:

$$amount - coin$$

can be extended by adding one current coin.

So we accumulate all such possibilities.

Small example verification

Suppose only coins $[1,2]$ and target $4$.

Possible combinations:

$1+1+1+1$
$2+1+1$
$2+2$

Total:

$$3$$

Running the DP gives exactly 3.

Final computation

Executing the program yields:

$$73682$$

Final verification

The result is:

positive,
reasonably large (many combinations exist),
consistent with the known Project Euler value.

So the computation is credible.

Answer: 73682

Project Euler Problem 31