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: the number of combinations.

Constraints

• amount up to 5000, coins up to ~300 values.
• Each coin may be used any number of times; ordering is irrelevant.

Example

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