OH !@#$%^&(), now I am really pi..ed.
I just wrote pseudocode and complexity estimation for 10 minutes, and when I post there is just the button "I am a human being" without any opportunity to enter something and my complete post is gone (and of course, this time I did not make a copy of the edit window, just in case ...), ok so here are the short version:
Number of Coins usually super monotone (i.e. each value is > than sum of previous values), therefor you can use greedy to get the exact coins for A.
Now use this multi set P of coins, add it to the (up to now empty) result set (a set of multisets), and to the (up to now empty too) working set.
Now repeat until the working set is empty:
Take set P out of the working set, P' = P, for each coin c in P: P' = P.replace(c, nextBiggerCoin), removeSmallestCoin(as long as P without smallest coin still > A)
If the P' is not yet in result set, put it into result set and working set
My guessed complexity was O(s*n^2), with s the number of solutions.