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?

$\endgroup$
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.

$\endgroup$
  • $\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 '18 at 13:23
  • $\begingroup$ @OctavioCastillo Right, I forgot about the m - 1, so my argument isn't correct. $\endgroup$ – orlp Jan 25 '18 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 '18 at 15:52

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.