Dynamic Programming Solution for a Variant of Coin Exchange

Question

I am practicing Dynamic Programming. I am focusing on the following variant of the coin exchange problem:

Let S = [1, 2, 6, 12, 24, 48, 60] be a constant set of integer coin denominations. Let n be a positive integer amount of money attainable via coins in S. Consider two persons A and B. In how many different ways can I split n among persons A and B so that each person gets the same amount of coins (disregarding the actual amount of money each gets)?

Example

n = 6 can be split into 4 different ways per person:

1. Person A gets {2, 2} and person B gets {1, 1}.
2. Person A gets {2, 1} and person B gets {2, 1}.
3. Person A gets {1, 1} and person B gets {2, 2}.
4. Person A gets {1, 1, 1} and person B gets {1, 1, 1}.

Notice that each way is non-redundant per person, i.e. we do not count both {2, 1} and {1, 2} as two different ways.

Previous research

I have studied at very similar DP problems, such as the coin exchange problem and the partition problem. In fact, there are questions in this site referring to almost the same problem:

• Dynamic Programming for a variant of the coin exchange - Here, OP studies the recursion relationship, but seems confused introducing the parity constraint.
• Coin Change :Dynamic Programming - Here, OP seems to pursue the reconstruction of the solution.
• Coin change(Dynamic programming) - Here, OP seems to also pursue the reconstruction of the solution.
• https://cs.stackexchange.com/questions/87230/dynamic-programming-for-a-variant-of-the-coin-exchange-problem - Here, OP seems to ask about a similar problem, yet parity, i.e. splitting into two persons, becomes the main issue.

I am interested mostly in the recursion relation that could help me solve this problem. Defining it will allow me to easily apply either a memoization of a tabulation approach to design an algorithm for this problem.

For example, this recursion:

def f(n, coins):
  if n < 0:
    return 0

  if n == 0:
    return 1

  return sum([f(n - coin, coins) for coin in coins])

Is tempting, yet it does not work, because when executed:

# => f(6, [1, 2, 6]) # 14

Here's an example of a run for S' = {1, 2, 6} and n = 6, in order to help me clarify the pattern (there might be errors):

Answer 1

This is what you can try:

Let C(n, k, S) be the number of distinct representations of an amount n using some k coins from S.

Then C(n, k, S) = sum(C(n - s_i, k - 1, S[i:])) The summation is for every s_i from S. S[i:] means all the elements from S starting from i-th element to the end - we need this to prevent repeated combinations.

The initial conditions are C(0, 0, _) = 1 and C(n, k, _) = 0 if n < 0 or k < 0 or n > 0 and k < 1 .

The number you want to calculate:

R = sum(C(i, k, S) * C(n - i, k, S)) for i = 1..n-1, k = 1..min(i, n-i)/Smin where Smin - the smallest coin denomination from S.

The value min(i, n-i)/Smin represents the maximum number of coins that is possible when partitioning the given sum. For example if the sum n = 20 and i = 8 (1st person gets $8, 2nd gets $12) and the minimum coin denomination is $2, the maximum possible number of coins is 8/2 = 4. You can't get $8 with >4 coins.