Understand The Algorithm Behind The Coin Change Problem With Mathematics

November 16, 2025

This content originally appeared on DEV Community and was authored by Ganesh Kumar

Hello, I’m Ganesh. I’m working on FreeDevTools online, currently building a single platform for all development tools, cheat codes, and TL; DRs — a free, open-source hub where developers can quickly find and use tools without the hassle of searching the internet.

Have you ever wondered how a vending machine knows exactly how to give you back your change? Or how computer programs figure out the most efficient way to group numbers?

I wanted to understand a mathematical concept called Integer Partitions and got to know how it powers one of the most famous algorithms in Computer Science.

Here is a straightforward breakdown of the logic, the code, and why it is so much faster and accurate.

What is a Partition?

In simple terms, an integer partition is a way of breaking a positive integer down into a sum of smaller positive integers. The order doesn’t matter, so 3+1 is treated the same as 1+3.

If we look at the number 4, there are exactly 5 partitions:

4
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1

In pure mathematics, you can use any number to make the sum. However, in Computer Science, we usually deal with Restricted Partitions. This is where the “Coin Change” question comes from: “Break a number into parts, but you can only use specific denominations (like 1, 2, and 5).”

Dynamic Programming

Trying to list every possible combination for a large number (like 100) would take ages. This is where Dynamic Programming shines. Instead of recalculating sums over and over, we build a table and remember the answers to smaller problems to solve the bigger ones.

The logic relies on splitting the problem into two groups for every coin we add:

Group A (Don’t use the coin): We keep the number of ways we found using previous coins.
Group B (Use the coin): We subtract the coin’s value from our target and look at the remainder.

The Formula:

\text{Total Ways} = \text{Ways without coin} + \text{Ways}(\text{Target} – \text{Coin})

A Walkthrough: Target 6

Let’s say we want to make the number 6 and we have coins with values {1, 2, 5}.

We solve this in layers. By the time we are calculating for coin 5, the computer already knows the “Old Ways” (using only 1s and 2s) is 4.

Old Ways (1s and 2s): 4 ways.
New Ways (using 5): We check the remainder: $6 - 5 = 1$ . We look at our table for Target 1, which has 1 way.

So, the math becomes simple addition:

\text{ (Old Ways)} + 1 \text{ (New Way)} = 5 \text{ total ways}

We didn’t have to guess; we just looked up the remainder in our table.

The Code

We can implement this logic in Python. The script below handles the “Unrestricted Partition” problem, where the available “coins” are every integer from 1 up to the target.

def count_unrestricted_partitions(target):
    # Coins are every integer from 1 up to the target
    # If target is 12, coins will be [1, 2, 3, ..., 12]
    coins = list(range(1, target + 1))

    # Create the table (indices 0 to target)
    ways_table = [0] * (target + 1)

    # Base Case: 1 way to make 0 (by doing nothing)
    ways_table[0] = 1

    # The Loop (The core logic)
    for coin in coins:
        for current_amount in range(coin, target + 1):
            # Formula: Old Ways + New Ways (Target - Coin)
            ways_table[current_amount] = ways_table[current_amount] + ways_table[current_amount - coin]

    return ways_table

# Test the code
my_target = 12
full_table = count_unrestricted_partitions(my_target)

print(f"Partitions for Target {my_target}: {full_table[my_target]} ways")

If you run this for a target of 12, the answer is 77. If you run it for 50, the number of ways jumps to over 200,000.

Why is this efficient?

You might wonder how fast this code is. In computer science, we measure this using Time Complexity.

If we tried to solve this using brute force (naive recursion), the complexity would be Exponential O(2T). For a target of 50, that would take quadrillions of operations and could take years to finish—which is almost 72,464 times the age of the universe.

However, the Dynamic Programming approach we used above has a Pseudo-Polynomial time complexity:

O(\text{Target} \times \text{Number of Coins})

Because we simply fill out a table using a nested loop, the computer only has to do a few thousand operations for a target of 50, solving it instantly.