LeetCode 518 Coin Change II - Implementation

Here's the full solution:

function change(amount, coins)
    dp := array of size (amount + 1), all 0
    dp[0] := 1
    // one way to make amount 0
    for each coin in coins
        for a from coin to amount
            dp[a] := dp[a] + dp[a - coin]
    return dp[amount]

Time: $O(n \times amount)$ where $n$ is number of coin types. Space: $O(amount)$.

The outer loop over coins (not amounts) prevents counting the same combination multiple times in different orders. If you swapped the loops, you'd count permutations instead of combinations.

This is unbounded knapsack for counting. The forward inner loop allows unlimited use of each coin.