Number of Ways To Make Change

Given a target amount and a set of denominations (coins), find the total number of ways the given target amount can be expressed by using the denominations provided. Consider you have an infinite supply of each denomination given in the array.

Dynamic Programming

We are essentially going to create an array with the size of the target number. This array will keep track of the number of ways we can use the coins in order to generate the amount at that particular index in the array.

For example, Consider target = 10.

So, we create an array of size 10+1, and fill it with 0s.

ways = [0,0,0,0,0,0,0,0,0,0,0];

Now, every index in the array, will represent the target sun. Therefore, arr[5] value will depict the number of ways to generate a target amount of 5 using the denominations.

Also, ways[0] will ALWAYS be 1 because there's essentially only 1 way to generate target of 0, which is using no coins at all.

The formula that is used is:

if (denom <= amount) {
    ways[amount] += ways[amount - denom]

So for example, ways[5] = ways[5] + ways[5 - 1] will be the formula IF we are traversing the 1 denomination value.

  • Iterate the denominations array
  • Iterate the ways array.
  • Check if denom <= amount. If Yes, use ways[amount] += ways[amount - denom] to update the array.
  • Return the last value in the ways array, because ways[target] is what we are interested in. And the last value will always be the target value in our case.

Time and Space Complexity

  • O(nd): Time where d is the number of denominations and n is the target value.
  • O(n): space where n is the target value.
Solve Number of Ways To Make Change on Algochurn

Practice all the solutions below

Practice the most popular front-end questions asked in coding interviews with   Frontend Churn