Coin change - number of ways

Problem Given coin denominations (unlimited supply of each) and a target amount, return the number of distinct combinations of coins that make up the amount (combinations, not permutations — order doesn't matter).

Input / Output

• Input: int array coins, int amount.
• Output: number of combinations.

Constraints

• amount up to 5000, coins up to ~300 values — O(coins * amount) DP.

Example

• coins = [1,2,5], amount = 5 → 4: (5), (2+2+1), (2+1+1+1), (1×5).

Expected approach

• Unbounded-knapsack counting DP: dp[0] = 1; for each coin c (outer loop), for s from c..amount: dp[s] += dp[s−c]. Looping coins outside is what counts combinations once; swapping the loops would count permutations — be ready to explain that distinction. O(n*amount) time, O(amount) space.