Coin Change Problem Enumeration Using N Coins And Each Denomination

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 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. {}).

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.

Replay

Pyth, 8 bytes

fqQsT^EE

Try it online!

Brute force much.

fqQsT^EE   Q is the first input, E second, E third
     ^EE   cartesian power, the second input raised to the third
f          filter for elements (as T) in which:
   sT          sum of T
 qQ            equals Q

Jelly, 8 bytes

ṗµS=⁵µÐf

Try it online!

Do I need to remove the duplicates?

Category: code golf Time: 2016-07-29 Views: 0

Related post

iOS development

Android development

Python development

JAVA development

Development language

PHP development

Ruby development

search

Front-end development

Database

development tools

Open Platform

Javascript development

.NET development

cloud computing

server

Copyright (C) avrocks.com, All Rights Reserved.

processed in 3.553 (s). 13 q(s)