Scala program for Counting change for a given amount and denominations

Problem Statement

Write a recursive function that counts how many different ways you can make change for an amount, given a list of coin denominations. For example, there are 3 ways to give change for 4 if you have coins with denomiation 1 and 2: 1+1+1+1, 1+1+2, 2+2.

How to think
First of all, sort the denomination set in ascending order.

Thumb Rule = Let a is the amount for which you have to find all the possible ways from a given denominations set S. Then the number of possible ways amount a can be achieved is equal to

• number of ways the amount a-S_max can be achieved using S +
• number of ways a can be achieved using S' = S - S_max i.e. removing the max element from S

Apart from the implementation of thumb rule, check that

1. if amount is negative, then we have crossed the limit and no way possible, so return 0
2. if amount is equal to 0, then the change has achieved through this branch, hence return 1
3. if max index is out of bound, then return 0

Program
Following function takes the amount and denomination's set, and returns the count of number of possible ways of getting change for the amount.

def countChange(money: Int, coins: List[Int]): Int = {

    val sortedCoins = coins.sorted

    def getCount(amount: Int, maxIndex: Int): Int = {

      if (amount < 0) 0
      else if (amount == 0) 1
      else if (maxIndex < 0) 0
      else getCount(amount - sortedCoins(maxIndex), maxIndex) + getCount(amount, maxIndex - 1)
    }

    getCount(money, coins.size - 1)
  }