1154. Coin Change II — Number of Ways

Given coin denominations (unlimited supply) and an amount, return the number of distinct combinations that make up 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: Four combinations.

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

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

Constraints

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

Asked by