And something not so useful

In an old Saturday Night Live, there was a fake ad for a bank that specialized in making change. That's all they did, but they were very good at it.

You have been hired by this fictitious bank to write a program for them that counts the number of possible ways to make change for a given amount of money. Let's assume that we are dealing with coins only and not concern ourselves with paper money.

Ultimately, you want a method that takes two arguments:

• The number of cents, as an integer.
• How many different kinds of coins can be used in the solution.

In addition, the following information is available in a class variable:

• An array of integers that contains the denominations of the coins. In American currency, this array would contain the values 1 5 10 25 50.

Thus the invocation countChange (100, 5) would ask how many ways there are make change for a dollar, using pennies, nickels, dimes and quarters and half-dollars. The answer is 292.

1. Have I given you enough information to solve this problem or is there more that needs to be specified? If the latter, then feel free to disambiguate in whatever way makes the implementation easiest.
2. Design an algorithm for doing this computation.
3. Implement it.

WARNING: This question is hard. I want you to think about it because it is worth thinking about. Even if you don't come up with an optimal answer, the process of thinking about it will be valuable.

CREDIT: This problem is taken from Abelson and Sussman, Structure and Interpretation of Computer Programs, MIT Press, 1987.