There are four types of common coins in &nbsp; [https://en.wikipedia.org/wiki/United_States US] &nbsp; currency: 
:::# &nbsp; quarters &nbsp; (25 cents)
:::# &nbsp; dimes &nbsp; (10 cents)
:::# &nbsp; nickels &nbsp; (5 cents), &nbsp; and 
:::# &nbsp; pennies &nbsp; (1 cent)  


There are six ways to make change for 15 cents:
:::# &nbsp; A dime and a nickel 
:::# &nbsp; A dime and 5 pennies
:::# &nbsp; 3 nickels
:::# &nbsp; 2 nickels and 5 pennies
:::# &nbsp; A nickel and 10 pennies
:::# &nbsp; 15 pennies
<br>

;Task:
How many ways are there to make change for a dollar using these common coins? &nbsp; &nbsp; (1 dollar = 100 cents).


;Optional:
Less common are dollar coins (100 cents); &nbsp; and very rare are half dollars (50 cents). &nbsp; With the addition of these two coins, how many ways are there to make change for $1000? 

(Note: &nbsp; the answer is larger than &nbsp; 2<sup>32</sup>).


;References:
* [https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book-Z-H-11.html#%_sec_Temp_52 an algorithm] from the book ''[[wp:Structure and Interpretation of Computer Programs|Structure and Interpretation of Computer Programs]]''.
* [https://algorithmist.com/wiki/Coin_change an article in the algorithmist].
* [[wp:Change-making problem|Change-making problem]] on Wikipedia.
<br><br>
