Skip to content

Instantly share code, notes, and snippets.

@mingan
Created September 27, 2012 17:01
Show Gist options
  • Save mingan/3795131 to your computer and use it in GitHub Desktop.
Save mingan/3795131 to your computer and use it in GitHub Desktop.
def countChange (money: Int, coins: List[Int]): Int = {
def count(money: Int, coins: List[Int]): Int = {
if (coins.tail.isEmpty) {
if (money % coins.head == 0) 1
else 0
}
else if (money == 0) 1
else if (money < coins.head) count(money, coins.tail)
else count(money - coins.head, coins) + count(money, coins.tail)
}
val sortedCoins = coins.sorted.reverse
if (coins.isEmpty || money < sortedCoins.last) 0
else count(money, sortedCoins)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment