class Solution:
  def countChange(self, denominations, total):
    
    def dp(index, acc, memo):
      if (index, acc) in memo:
        return memo[(index, acc)]

      if acc == total:
        return 1

      if acc > total or index == len(denominations):
        return 0

      with_item = dp(index, acc + denominations[index], memo) 
      without_item = dp(index + 1, acc, memo)

      result = with_item + without_item
      memo[(index, acc)] = result

      return result
    
    return dp(0, 0, {})