This can be solved by Dynamic Programming.
Let the denominations be d1,d2,...,dn and their corresponding numbers
be P1,P2,...,Pn. Let C(n,S) be the matrix which tells us if the amount
S can be obtained by using coins d1,...,dn.
Then C(n,S) = C(n-1,S) if denomination dn is not used, else
C(n,S) = C(n,S-Pn), Pn = Pn-1 --> if Pn > 0
else = C(n-1,S) if Pn == 0
Also note that C(a,A) = 1 if A is a multiple of dp and A < dp * Pa.
So the matrix C can be filled up column wise. So C(n,S) = 1 if C(n-1,S)
= 1
else C(n,S) = C(n,S-Pn) if Pn > 0 else C(n,S) =
If C[S] is 1 at the end, then the sum S can be obtained else it can't
be.
