1133. Count Ways to Make Change for Amount

Given an amount and an array of distinct coin denominations (unlimited supply of each), return the number of distinct combinations of coins that sum exactly to the amount. Order does not matter. The input is JSON {amount, coins}.

Input: JSON {amount, coins}.

Output: Integer — the number of combinations.

Examples

Input: {"amount":5,"coins":[1,2,5]}
Output: 4
Explanation: 5, 2+2+1, 2+1+1+1, 1x5.

Input: {"amount":3,"coins":[2]}
Output: 0
Explanation: Cannot form 3.

Input: {"amount":0,"coins":[7]}
Output: 1
Explanation: The empty combination.

Constraints

• 0<=amount<=5000
• 1<=coins<=300

Asked by