# Compute all possible coin changes for a given amount

DEN=[1,5,10,25]

def print_all(amount, change)
# control: backtracking
# invariant: amount+sum(change) is constant
  if amount == 0
    p change
  elsif amount>0
    DEN.each { |x|
      if change == [] || x >= change[0]
        print_all(amount-x, [x]+change)
      end
    }
    # else amount < 0, overshot, forget it
  end
end

# An example, 17 cents
print_all(17, [])