Let's say we have a bunch of coins with denominations $d_1, d_2,\ldots,d_n$ and a target sum $M$. Is it possible to count the total number of ways I can select exactly $N$ coins (with replacement) that add up to $M$?

For example, if the denominations are $0.05, 0.10, 0.15, 0.20, 0.50$ and the total $M = 0.75$, there are 12 permutations of $N = 3$ coins that total to $M$.

If possible, I would prefer to count the number of permutations, but combinations are acceptable as well.

I understand this is a dynamic programming problem but I was wondering if there's a way of counting the number of solutions.

I have found several related questions such as [fixed sum combinations]{Fixed sum of combinations} and [number of ways to select a sum with limited number of elements]{Number of ways to select a sum with limited number of elements} but there are some differences.

  • $\begingroup$ Does it help that the dynamic programming solution can be adapted to also count the number of solutions? $\endgroup$ – Misha Lavrov Apr 5 '17 at 3:28
  • $\begingroup$ @MishaLavrov I am interested in alternative, non dynamic programming solutions but yes, thank you for making that point. $\endgroup$ – undefinederrorname Apr 5 '17 at 3:37

Generating functions can help. Specifically:

$$ f(x) = (x^{d_1} + x^{d_2} + ... + x^{d_m})^N $$

where the exponents $ d_1, d_2, ..., d_m$ are the denominations, $N$ is the size of configuration (number of coins to be used), and (after expanding) the coefficient of $x^M$ represents the number of configurations of $N$ coins that add to $M$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.