Coin Change Problem Enumeration Using N Coins And Each Denomination

Question

The coin change problem is very well documented. Given an infinite supply of coins of denominations x_1 to x_m you need to find the number of combinations which add up to y. For example, given x = {1,2,3} and y = 4 we have four combinations:

1. {1,1,1,1}
2. {1,1,2}
3. {1,3}
4. {2,2}

Introduction

There are several variations of the coin change problem. In this variation we have two additional restrictions:

1. Every denomination must be used at least once.
2. Exactly a fixed number of coins must be used in total.

For example, given x = {1,2,3}, y = 36 and n = 15 where n is the total number of coins that must be used, we get four combinations:

1. {1,2,2,2,2,2,2,2,3,3,3,3,3,3,3} (1 ones, 7 twos, 7 threes)
2. {1,1,2,2,2,2,2,3,3,3,3,3,3,3,3} (2 ones, 5 twos, 8 threes)
3. {1,1,1,2,2,2,3,3,3,3,3,3,3,3,3} (3 ones, 3 twos, 9 threes)
4. {1,1,1,1,2,3,3,3,3,3,3,3,3,3,3} (4 ones, 1 twos, 10 threes)

Challenge

The challenge is to write a function enumerate in the language of your choice which enumerates all the combinations as described above given:

1. The list of denominations. For example {1,5,10,25}. You may use either lists or arrays.
2. A non-negative integer y that denotes the sum of every combination.
3. A non-negative integer n that denotes the total number of coins.

The order of the arguments doesn't matter. Pointfree functions are allowed.

The output of the enumerate function must be a list of combinations. Each combination must be unique and it must be a list of n integers which add up to y. Every denomination must appear at least once in each combination and no combination must be missing. The ordering of the integers and the combinations doesn't matter. You may use either lists or arrays for the output.

Keep in mind the following edge cases:

1. If both y and n are zero and the list of denominations is empty then the output is a list of one combination, the empty combination (i.e. {{}}).
2. Otherwise, if y is zero, n is zero or the list of denominations is empty then the output is a list of zero combinations (i.e. {}).
3. More generally, if y is less than the sum of the denominations or n is less than the number of denominations then the output is a list of zero combinations.

Scoring will be based on the size of the entire program in bytes. Note that this includes the enumerate function, helper functions, import statements, etc. It does not include test cases.

Answer 1

05AB1E, 20 bytes

g-¹sã€{Ùvy¹«DO³Qiˆ}¯

Input is in the order: list of values, nr of coins, sum to reach.

Explanation in short

1. Get all permutations of the coin list of length: final length - length of unique coin list
2. Add the list of unique coins to these lists.
3. If the sum equals the sought after sum, save the list
4. Output all saved lists

Try it online

The online compiler can't handle large number of coins.

Answer 2

MATL, 22 bytes

Z^!S!Xu!tsi=Z)"1G@m?@!

Input order is: array of denominations, number of coins taken (n), desired sum (y).

Each combination is displayed on a different line. Empty output is displayed as an empty string (so nothing).

Try it online!

The code runs out of memory in the online compiler for the example in the challenge, but works offline with a standard, reasonably modern computer:

>> matl
 > Z^!S!Xu!tsi=Z)"1G@m?@!
 > 
> [1 2 3]
> 15
> 36
1 1 1 1 2 3 3 3 3 3 3 3 3 3 3
1 1 1 2 2 2 3 3 3 3 3 3 3 3 3
1 1 2 2 2 2 2 3 3 3 3 3 3 3 3
1 2 2 2 2 2 2 2 3 3 3 3 3 3 3

Explanation

Z^      % Implicitly input array of denomminations and number of coins n. Compute 
        % Cartesian power. This gives 2D array with each "combination"
        % on a different row
!S!     % Sort each row
Xu      % Deduplicate rows
!       % Transpose: rows become columns. Call this array A
ts      % Push a copy, compute sum of each column
i       % Input y (desired sum)
=       % Logical array that contains true if the "combination" has the desired sum
Z)      % Keep only those columns in array A
"       % For each column
  1G    %   Push array of denominations again
  @     %   Push current column
  m     %   Is each denomination present in the column?
  ?     %   If so
    @!  %     Push current column again. Transpose into a row
        %   End if
        % End for
        % Implicitly display stack contents

Answer 3

Python 3, 120 106 bytes

from itertools import*
lambda d,t,l:[i+d for i in combinations_with_replacement(d,l-len(d))if sum(i+d)==t]

An anonymous function that takes input of a tuple of denominations of the form (x_1, x_2, x_3 ... , x_k), a target value, and a number of coins via argument, and returns a list of tuples of the form [(solution_1), (solution_2), (solution_3), ... (solution_k)].

How it works

Itertools's combinations_with_replacement function is used to generate all l-len(d) combinations, with replacement, of the denominations. By appending d to each of these combinations, it is guaranteed that each denomination appears at least once, and that the new combination has length l. If the elements of a combination sum to t, the combination is added to the return list as a tuple.

Try it on Ideone

---

An alternative method for 108 bytes

from itertools import*
lambda d,t,l:set(tuple(sorted(i+d))for i in product(d,repeat=l-len(d))if sum(i+d)==t)

An anonymous function that takes input of a tuple of denominations of the form (x_1, x_2, x_3 ... , x_k), a target value, and a number of coins via argument, and returns a set of tuples of the form {(solution_1), (solution_2), (solution_3), ... (solution_k)}.

How it works (other version)

This uses the product function from itertools to generate all l-len(d) arrangements of the denominations. By appending d to each of these combinations, it is guaranteed that each denomination appears at least once, and that the new combination has length l. If the elements of a combination sum to t, the combination is sorted, converted from a list to a tuple, and added to the return tuples. Finally, calling set removes any duplicates.

Try it on Ideone (other version)

Answer 4

JavaScript (ES6), 135 bytes

g=(a,n,y,r)=>n>0?y>0&&a.map((x,i)=>g(a.slice(i),n-1,y-x,[...r,x])):n|y||console.log(r)
(a,n,y)=>g(a,n-a.length,a.reduce((y,x)=>y-x,y),a)