solution for "count change" problem

balance.scala

def balance(chars: List[Char]): Boolean = {
  def inner(chars: List[Char], sum: Int): Boolean = {
    if (chars.isEmpty)
      sum == 0
    else {
      val c = chars.head.toString()
      var newSum = sum
      if (c.equals("("))
        newSum += 1
      else if (c.equals(")"))
        newSum -= 1
      if (newSum < 0)
        false
      else
        inner(chars.tail, newSum)
    }
  }

  inner(chars, 0)
}


// balance("((hello)())".toList)

pascal.scala

  /**
   * Exercise 1
   */
    def pascal(c: Int, r: Int): Int = {
      if (c > r)
        throw new IndexOutOfBoundsException("Column index must be equal to or less than row")
      if (c < 0 || r < 0)
        throw new IndexOutOfBoundsException("Column and row must be equal to or greater than zero (0)")
      if (c == 0 || c == r)
      // edge of triangle
        1
      else
        pascal(c - 1, r - 1) + pascal(c, r - 1)
    }

practice01.03.scala

  /**
    * Exercise 3
    * @author: michaelbutler
    */
  def countChange(money: Int, coins: List[Int]): Int = {

    // We can prevent duplicate operations by adding a cache memoization
    // (money,coins) -> (combinations)
    var cacheMap = mutable.HashMap[String, List[String]]()

    def generateCombinations(money: Int, coins: List[Int]): List[String] = {
      if (money == 0) {
        // Success case
        List("")
      } else if (getCache(money, coins) != null) {
        getCache(money, coins)
      } else {
        var combos = List[String]()
        var coinsList = coins
        while (coinsList.nonEmpty) {
          if (money - coinsList.head >= 0) {
            for (subList <- generateCombinations(money - coinsList.head, coinsList)) {
              val listWithPrepend = coinsList.head.toString + subList
              combos = combos ++ List(listWithPrepend.sorted)
            }
          }
          coinsList = coinsList.tail
        }
        setCache(money, coins, combos)
      }
    }

    /**
      * Generate a cache key string
      * @param keyMoney
      * @param keyCoins
      * @return
      */
    def genKey(keyMoney: Int, keyCoins: List[Int]): String = {
      keyMoney.toString + "," + keyCoins.sorted.toString()
    }

    /**
      * Cache a computed value by keyMoney/keyCoins
      * @param keyMoney Money amount, e.g. 4
      * @param keyCoins Available coins list, e.g. (1, 2)
      * @param value Resulting combinations to cache, e.g. ("1111", "112", "22")
      * @return
      */
    def setCache(keyMoney: Int, keyCoins: List[Int], value: List[String]): List[String] = {
      val key = genKey(keyMoney, keyCoins)
      cacheMap += (key -> value)
      value
    }

    /**
      * Get the pre-computed value in cache. If not exists, null
      * @param keyMoney
      * @param keyCoins
      * @return
      */
    def getCache(keyMoney: Int, keyCoins: List[Int]): List[String] = {
      val key = genKey(keyMoney, keyCoins)
      cacheMap.getOrElse(key, null)
    }

    if (money == 0 || coins.isEmpty) {
      0
    } else {
      generateCombinations(money, coins.sorted.reverse).size
    }
  }
// Run with:
// countChange(300, List(5,10,20,50,100,200,500)) === 1022