Diwali Offer!Flat 20% OFF
Enroll Now
PrakalpanaLive online tech training

165. Coin Change II

MediumDay 48 of 60Dynamic Programming

Given an integer amount and an array coins of distinct denominations (unlimited supply of each), return the number of combinations of coins that make up exactly amount. Order does not matter, so 1 + 2 and 2 + 1 count once. If no combination works, return 0.

Example 1
Input: amount = 5, coins = [1,2,5]
Output: 4
5, 2 + 2 + 1, 2 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1.
Example 2
Input: amount = 3, coins = [2]
Output: 0
Constraints
  • 1 <= coins.length <= 300
  • 1 <= coins[i] <= 5000
  • All coins are distinct
  • 0 <= amount <= 5000
  • The answer fits in a signed 32-bit integer
Hints
Frequently asked at: Amazon, Google, Goldman Sachs
Ctrl + Enter runs the examples

Not sure what to learn next?

A 1-on-1 session with an industry mentor and a roadmap built for you. How it works

  1. 1Discuss your goals
  2. 2Get a personal plan
  3. 3Start learning
Book for β‚Ή200/ 30 min