• 1 ≤ coins.length ≤ 300
• 1 ≤ coins[i] ≤ 5000
• 0 ≤ amount ≤ 5000
• All denominations are distinct and available in unlimited quantity
• The answer fits in a signed 32-bit integer

You have coins of a few fixed values, each in unlimited supply. Count how many different combinations add up to an exact amount. The catch is one word: order does not matter.

For amount = 3 with coins = [1, 2], the answer is 2, not 3. The combinations are {1,1,1} and {1,2}. Writing the second as 2+1 is the same handful of coins, not a new answer.

This is the whole difficulty. If we are not careful, we count 2+1 and 1+2 as two and get the wrong number. Let us see exactly where that slip happens.

A first attempt: let g(a) be the number of ways to make a, and say the last coin was some c:

g(a) = sum over every coin c <= a of g(a - c)

Run it on coins = [1, 2], amount = 3: g(0)=1, g(1)=1, g(2)= g(1)+g(0) = 2, g(3) = g(2)+g(1) = 3. It says 3, but the true answer is 2.

Why? Because "the last coin was 1" and "the last coin was 2" describe orders. The combination {1,2} gets counted once as (a 1, then a 2) and again as (a 2, then a 1). The formula is not broken — it correctly counts ordered sequences. It just answers a different question than the one asked.

I go through the coins one at a time, from the last toward the first — a fixed order, so I never count the same combination twice. Standing at coin i with amount a still to make, I have two moves:

I am counting ways, so I add the two. The two things I track are which coin I'm on (i) and how much is left to make (a).

f(i, a) = f(i-1, a) + ( f(i, a - coins[i]) if coins[i] <= a )

The staying-on-i move is how "unlimited copies" is expressed while keeping the coins in a fixed order.

Base cases:

We start by asking about the last coin with the full amount: f(n-1, amount).

def change(amount, coins):
    n = len(coins)
    memo = {}

    def f(i, a):
        if a == 0: return 1
        if i == 0: return 1 if a % coins[0] == 0 else 0
        if (i, a) in memo: return memo[(i, a)]
        ways = f(i - 1, a)                       # stop using coin i
        if coins[i] <= a:
            ways += f(i, a - coins[i])           # use another coin i; stay put
        memo[(i, a)] = ways
        return ways

    return f(n - 1, amount)

States are pairs (i, a), giving n × (amount+1) of them and O(N × amount) time.

Now the table, straight from the recurrence. Let dp[i][a] hold what f(i, a) returned, and swap each call for an array read:

dp[i][a] = dp[i-1][a] + ( dp[i][a - coins[i]] if coins[i] <= a )

The skip branch reads row i-1, so fill the rows upward. The take branch reads the same row at a smaller amount, so within a row sweep the amount upward too. The base cases copy straight over: row 0 is dp[0][a] = 1 if a % coins[0] == 0 else 0, and column a = 0 is 1 in every row:

def change(amount, coins):
    n = len(coins)
    dp = [[0] * (amount + 1) for _ in range(n)]

    for a in range(amount + 1):                  # row 0: only the first coin
        dp[0][a] = 1 if a % coins[0] == 0 else 0
    for i in range(n):
        dp[i][0] = 1                             # amount 0: the empty combination

    for i in range(1, n):
        for a in range(1, amount + 1):
            dp[i][a] = dp[i - 1][a]
            if coins[i] <= a:
                dp[i][a] += dp[i][a - coins[i]]

    return dp[n - 1][amount]

Row i reads row i-1 and itself, so a single array works — and the result is the version most people memorise without understanding:

def change(amount, coins):
    dp = [0] * (amount + 1)
    dp[0] = 1
    for c in coins:                     # coin loop OUTSIDE
        for a in range(c, amount + 1):  # amount loop inside, ascending
            dp[a] += dp[a - c]
    return dp[amount]

Keep the pair together:

The ascending amount sweep means a coin may be reused, which is exactly what unlimited supply needs.

Coin 1, sweeping a from 1 to 5, each dp[a] += dp[a-1]:
dp = [1, 1, 1, 1, 1, 1]. One way to make each amount, using only 1s. Correct.

Coin 2, sweeping a from 2 to 5:
- a=2: dp[2] += dp[0] → 1 + 1 = 2 ({1,1} and {2})
- a=3: dp[3] += dp[1] → 1 + 1 = 2 ({1,1,1} and {1,2})
- a=4: dp[4] += dp[2] → 1 + 2 = 3 ({1,1,1,1}, {1,1,2}, {2,2})
- a=5: dp[5] += dp[3] → 1 + 2 = 3 ({1×5}, {1,1,1,2}, {1,2,2})

Coin 5, sweeping a from 5 to 5:
- a=5: dp[5] += dp[0] → 3 + 1 = 4 (the new one is {5})

Answer 4: {1,1,1,1,1}, {1,1,1,2}, {1,2,2}, {5}. Listing them by hand confirms it.

Whenever a problem asks "how many ways", settle one thing first, before writing anything: do two selections that differ only in order count once or twice? The answer decides your state and your loop order. Get it wrong and you produce a plausible-looking number that is not the answer to the question asked.

The cure for unordered counting is always the same: pick one fixed order to build things in, and never go back to an earlier item. Here it showed up as the coin loop on the outside; elsewhere it shows up as a start index handed down a recursion. Same idea, different costume.