Coin Change Ways
Problem
You are given a list of coin denominations and a target amount. Each denomination is available in unlimited supply. Count how many distinct combinations of coins add up exactly to amount. Order does not matter: {2, 1} and {1, 2} are the same combination.
Examples
Example 1 — coins = [1, 2, 5], amount = 5 → 4
The combinations are {5}, {2, 2, 1}, {2, 1, 1, 1} and {1, 1, 1, 1, 1}.
Example 2 — coins = [2], amount = 3 → 0
No way to make an odd amount from 2s.
Edge — amount = 0 → 1 (the empty combination).
Constraints
1 <= len(coins) <= 300,1 <= coin <= 5000, denominations are distinct.0 <= amount <= 5000.- The answer can be large; return it modulo
10^9 + 7in the OA version.
What they look for
A 1-D DP table ways[x] where the outer loop is over coins and the inner loop is over amounts. Swapping the loops counts ordered sequences instead of combinations, and that is the single most common wrong answer we see. I will ask you to explain, with the [1, 2] / amount = 3 case, why the loop order matters. The recursive version with memoisation is acceptable if you can state its complexity.