Here's the full solution:
plaintext function change(amount, coins) dp := array of size (amount + 1), all 0 dp[0] := 1 // one way to make amount 0 Each coin in coins for a from coin to amount dp[a] := dp[a] + dp[a - coin] return dp[amount]
Time: O(n×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.