2
$\begingroup$

I am interested in solving a variant of the coin exchange problem. Recall the formal definition of the coin exchange problem:

Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = {S1, S2, .. , Sm} integral-valued coins, how many ways can we make the change? The order of coins doesn’t matter. For example, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4. For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. So the output should be 5. See here for further detail.

Here, one can find a tabulation-DP-based solution for this problem. This solution is based on the following recurrence relation:

count(S, m, n) = count(S, m - 1, n) + count(S, m, n - S[m - 1]);

With base cases:

count(S, m, n < 0) = 0
count(S, m, n = 0) = 1
count(S, m <= 0, n >= 1) = 0

Intuitively, this recurrence relation defines a problem as the solution to two sub-problems: Those in where we discard coins, and those for which we assume the coins a progressively used once at the time.

Question: How can I modify this recurrence relation to count the number of ways we can sum to N disregarding order and with an even number of summands? For example, for N = 4 and S = {1,2,3}, there are four solutions total (disregarding order): {1,1,1,1},{1,1,2},{2,2},{1,3}, but only 3 of them have an even number of summands, i.e. {1,1,1,1},{2,2},{1,3}.

Previous research: At first I thought I could double the requested sum for the case of discarding coins, and requesting that each coin is consumed twice for the cases in where we would use some of the coins, i.e.:

count(S, m, n) = count(S, m - 1, 2*n) + count(S, m, n - 2*S[m - 1]);

This works for some sample cases, but it does not work. Any hints?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Add a parity parameter to $C$ and check for it in the base case, making the wrong parity invalid:

$$ \newcommand{\for}{\text{for }} C(S, m, n, p) = \begin{cases} 0& \for n < 0\\ 0& \for n = 0 \wedge p = 1\\ 1& \for n = 0 \wedge p = 0\\ 0& \for m = 0\\ C(S,m-1,n,p) + C(S, m,n-S_m, 1-p)& \text{otherwise} \end{cases} $$

Note that I'm using mathematical notation above so $S$ and $m$ are using one-based indices.

Since we want only an even number of summands we want $p = 0$, thus $C(S, m, n, 0)$ gives the answer you want.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks a lot. As far as the incorrect base case... when m== 0, I would be accessing S[m - 1] i.e. S[- 1] which would yield an incorrect access method. Do you mind better clarifying why is the base case wrong? $\endgroup$
    – Octavio Castillo
    Jan 25, 2018 at 13:23
  • $\begingroup$ @OctavioCastillo Right, I forgot about the m - 1, so my argument isn't correct. $\endgroup$
    – orlp
    Jan 25, 2018 at 13:33
  • $\begingroup$ What about if I need to account for duplicates in the solutions? For example, for S = [1, 2, 6] and n = 6, the answer would be 4 instead of 2 because 1 + 1 + 2 + 2 and 2 + 2 + 1 + 1 and 2 + 1 + 2 + 1 would account for 3 different solutions each, alongside the 1 + 1 + 1 + 1 + 1 + 1 solution. $\endgroup$
    – Octavio Castillo
    Feb 9, 2018 at 15:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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