Coin Change 2

Advanced

You're a young explorer on a quest to find a hidden treasure. According to ancient maps, to unlock the treasure chest, you need to find the exact amount of gold coins. However, your treasure bag contains various denominated coins! But fret not, your task is to figure out the different ways you can combine these coins to make up a specific amount. Let's use Python to solve this!

Write a function coin_change_ways that calculates the number of different combinations that can make up a given amount using a set of coin denominations. You have an unlimited number of each type of coin.

Examples:

# Example 1 coin_change_ways(5, [1, 2, 5]) # Output: 4 # Explanation: There are four ways to make change for 5: # (1=5), (2+2+1), (1+1+1+1+1), (5) # Example 2 coin_change_ways(3, [2]) # Output: 0 # Explanation: No combination can make 3 with only denomination 2. # Example 3 coin_change_ways(10, [10]) # Output: 1 # Explanation: There is only one way to make 10 which is (10).

Hints:

  • Think about how you can use dynamic programming to store the number of ways to make each amount incrementally.
  • Start with an array ways where ways[i] represents the number of ways to create the amount i.
  • Initialize ways[0] to 1 because there is one way to make the amount 0: using no coins at all.
Geek
Inputs

Arg 1:

5

Arg 2:

[1,2,5]
Expected Output
4
Actual Output
Coin Change 2 [advanced] | Coding for Kids