Here is a mathematical problem is known as the postage stamp problem. You need to put a certain number of cents of postage on an envelope (amount). There is room on the envelope for only n stamps (but no more). There is a list of the available denominations of stamps (denominations). You can use as many of each denomination as you need. Can you get the required amount of postage? For example, for amount=12, n=3, and denominations=<<9 5 2>> you can do it with 5+5+2. But you could not make amount=17 at all. Write a recursive method public static boolean canMake(int amount, int n, IntLinkList denominations) which will return true if you can make the given amount using at most n stamps of the given denominations. The function should work for amount>= 0, n>=0, and denominations that are all >0, in descending order, with no duplicates. The list of denominations might be empty (length 0). canMake(12, 3, new IntLinkList(new int[]{9,5,2})) should return true. canMake(17, 3, new IntLinkList(new int[]{9,5,2})) should return false. The supplied TestA5Q4 file contains a main program which will test your method by reading n and denominations from the user, and then trying all amounts from 0 up to n times the largest denomination.

Here is one possible test run:

How many stamps fit on an envelope?

3

What denominations are available? (in ascending order, all on one line):

2 5 9

Make 0 from 3 of <<9 5 2 >>: true

Make 1 from 3 of <<9 5 2 >>: false

Make 2 from 3 of <<9 5 2 >>: true

Make 3 from 3 of <<9 5 2 >>: false

Make 4 from 3 of <<9 5 2 >>: true

Make 5 from 3 of <<9 5 2 >>: true

Make 6 from 3 of <<9 5 2 >>: true

Make 7 from 3 of <<9 5 2 >>: true

Make 8 from 3 of <<9 5 2 >>: false

Make 9 from 3 of <<9 5 2 >>: true

Make 10 from 3 of <<9 5 2 >>: true

Make 11 from 3 of <<9 5 2 >>: true

Make 12 from 3 of <<9 5 2 >>: true

Make 13 from 3 of <<9 5 2 >>: true

Make 14 from 3 of <<9 5 2 >>: true

Make 15 from 3 of <<9 5 2 >>: true

Make 16 from 3 of <<9 5 2 >>: true

Make 17 from 3 of <<9 5 2 >>: false

Make 18 from 3 of <<9 5 2 >>: true

Make 19 from 3 of <<9 5 2 >>: true

Make 20 from 3 of <<9 5 2 >>: true

Make 21 from 3 of <<9 5 2 >>: false

Make 22 from 3 of <<9 5 2 >>: false

Make 23 from 3 of <<9 5 2 >>: true

Make 24 from 3 of <<9 5 2 >>: false

Make 25 from 3 of <<9 5 2 >>: false

Make 26 from 3 of <<9 5 2 >>: false

Make 27 from 3 of <<9 5 2 >>: true