The Difference Between Unrestricted and Restricted Integer Partitions

#inegral #dynamic

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.

In my previous post, I explored the "Coin Change" problem—specifically, calculating the number of ways to form a target sum. After publishing, I received a thoughtful comment from a reader that highlighted a few nuances in my implementation.

They pointed out that my original solution treated the problem as an "Integer Partition" (where you have an infinite supply of every integer from 1 to N) rather than a "Vending Machine" scenario (where you have specific denominations like 1, 5, and 10). They also asked a critical question: How does the order of the loops ensure we are counting combinations and not permutations?

This feedback sent me back to the drawing board to refine the algorithm.

Here is what I learned about unrestricted vs. restricted partitions and the importance of loop order in Dynamic Programming.

From Infinite to Finite

My original code generated coins using range(1, target + 1). In pure mathematics, this is correct for calculating integer partitions. However, in software engineering—and vending machines—we rarely have coins of every single integer value.

We usually have a fixed set, like {1, 5, 10 ..}.

As, we don't have 2 cent or 3 cent coins.

To make the function practical for real-world scenarios, I needed to change the input to accept a specific list of denominations.

Here is the updated implementation:

def count_restricted_partitions(target, coins):
    # Initialize the table with 0
    # We need 'target + 1' slots to include index 0 up to index target
    ways_table = [0] * (target + 1)

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

    # The Core Logic
    for coin in coins:  # Outer Loop
        for current_amount in range(coin, target + 1): # Inner Loop
            ways_table[current_amount] += ways_table[current_amount - coin]

    return ways_table[target]

# Test the code
my_target = 10
my_coins = [1, 5, 10] #(USD)
result = count_restricted_partitions(my_target, my_coins)

print(f"Ways to make {my_target}: {result}")

The Loop Order

The most interesting part of this algorithm is the structure of the loops.

You will notice I placed the coins loop on the outside and the amount loop on the inside. This is not an arbitrary choice; it determines whether you are counting combinations or permutations.

1. Outer Loop = Coins (Combinations)
By iterating through the coins in the outer loop, we process one denomination completely before moving to the next.

First, we find all ways to make sums using only 1s.
Then, we update the table using 5s.
Finally, we update the table using 10s.

Because we finish with the 1s before we ever touch the 2s, we can never go "backwards."

We count the set {1, 2} effectively, but we never count {2, 1} as a separate entry. This treats the order as irrelevant, which is exactly what we want for coin change.

2. Outer Loop = Amount (Permutations)
If we swapped the loops—iterating through the amounts first (1 to 100) and checking every coin for every amount—we would count every sequence. {1, 2} and {2, 1} would be counted as two distinct ways.

Dynamic Programming

Another point of confusion that often arises is why this solution looks like a "simple loop" rather than a complex recursive function.

This approach is known as Bottom-Up Dynamic Programming (or Tabulation).

Instead of starting at the target (say, 100) and recursively asking "what if I subtract 5?", we start at 0 and build our way up. It is essentially filling out a cheat sheet. When the loop reaches current_amount = 10, it doesn't need to calculate the answer for 10 - 5; it just looks back at index 5 in the table, where the answer is already waiting.

Conclution

The feedback from the previous post helped clarify the distinction between mathematical partitions and the classic coin change problem.

Restricted Partitions: Pass a specific list of coins (e.g., [1, 5, 10, 25]) rather than a range.
Combinations: Keep the coin iteration as the outer loop to ensure {1, 5} is treated the same as {5, 1}.
Efficiency: Using a bottom-up table approach allows us to solve this in pseudo-polynomial time, which is significantly faster than naive recursion.

Next time you need to calculate arrangements of items where order doesn't matter, remember to check your loop order—it makes all the difference.