Given an integer amount and an array coins of distinct denominations (unlimited supply of each), return the number of combinations of coins that make up exactly amount. Order does not matter, so 1 + 2 and 2 + 1 count once. If no combination works, return 0.
5, 2 + 2 + 1, 2 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1.- 1 <= coins.length <= 300
- 1 <= coins[i] <= 5000
- All coins are distinct
- 0 <= amount <= 5000
- The answer fits in a signed 32-bit integer
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force recursion picks how many of each coin to use, which is exponential. State: dp[i][a] = ways to make a using only the first i coins. Recurrence: either use no more of coin i (dp[i - 1][a]) or use one more of it (dp[i][a - coin]), so dp[i][a] = dp[i - 1][a] + dp[i][a - coin]. Base case: dp[i][0] = 1 (the empty combination). Since row i only reads row i - 1 and itself, one 1D array works if the coin loop is outer: then every combination is built in a fixed coin order and is counted once. Swapping the loops would count 1 + 2 and 2 + 1 separately.
Algorithm
- Create
dpof sizeamount + 1withdp[0] = 1and the rest 0. - For each coin
c(outer loop): - For
afromctoamount(increasing, so the same coin can be reused), adddp[a - c]todp[a]. - Return
dp[amount].
O(amount * coins.length)Space: O(amount)dp values for amounts you never need can exceed it. In C++ signed overflow is undefined behaviour, so use unsigned long long (wrap-around is well defined) and cast at the end. Python ints never overflow, and Java wraps silently.class Solution: def change(self, amount: int, coins: List[int]) -> int: dp = [0] * (amount + 1) # dp[a] = ways to make a dp[0] = 1 for c in coins: # coin loop outside, so each combination is counted once for a in range(c, amount + 1): dp[a] += dp[a - c] return dp[amount]