Subset Sum Problem

Imagine that you are implementing the logic for a digital cash register. Whenever a customer needs change, you would like to display a message that tells the cashier whether or not the money currently in the register can be combined in some way so that its sum is equal to the amount of change required. For example, if a product costs $7.50 and the customer pays $10.00, the message would report whether the money in the register can be used to produce exactly $2.50 in change.

Let's say that the register currently contains ten quarters (10 x $0.25), four dimes (4 x $0.10), and six nickels (6 x $0.05). We can easily conclude that the target sum of $2.50 can be formed in the following ways:

10 quarters                    -> $2.50

9 quarters, 2 dimes, 1 nickel -> $2.25 + $0.20 + $0.05

9 quarters, 1 dime, 3 nickels -> $2.25 + $0.10 + $0.15

9 quarters, 5 nickels   ...