Small un-optimized attempt at calculating how many unique ways there are too make a particular amount of money with the provided increments. This uses change * 100 to work exclusively with integers.

tail_recursive_change_maker.rb

require 'singleton'

CHANGE_VALUES = [1, 5, 10, 25, 50, 100].reverse
TARGET_VALUE = 100

class ReportTiming
  include Singleton

  def initialize
    reported
  end

  def reported
    @last_report_time = Time.now.to_i
  end

  def should_report?
    (Time.now.to_i - @last_report_time) > 1
  end
end

class Array
  def sum
    self.inject(&:+) || 0
  end
end

def add_till_target(current = [], depth = 0)
  return [] if current.sum > TARGET_VALUE
  valid_solutions = []

  if ReportTiming.instance.should_report?
    puts "Current: depth=#{depth} sum=#{current.sum} current=#{current.join(',')}"
    ReportTiming.instance.reported
  end

  CHANGE_VALUES.map do |ch|
    new_round = current + [ch]
    (valid_solutions << new_round) && next if new_round.sum == TARGET_VALUE
    add_till_target(new_round, depth).each { |s| valid_solutions << s }
  end

  valid_solutions
end

puts add_till_target.count