# Can this value be made with unique coins and/or notes?

Write a program which calculates if an inputted monetary value, as an integer, can be represented by a unique combination of coins and/or notes, that meaning the same coin/note cannot be used more than once.

Your program should take a value as input, and can take a list of coin/note values either via input or via your language's equivalent of an array. The list of coins/notes should be able to change, so make sure it's clear where this is defined if you're using a constant.

Your program should output any truthy/falsy value respectively.

Please note that outputting the list of coins/notes that make up the value is not required.

# EXAMPLE

Using the UK pound, (£1.00 = 100 and £420.69 = 42069)

coins = [1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000]


The following will output true:

6 (1, 5)
15 (10, 5)
88 (1, 2, 5, 10, 20, 50)
512 (500, 10, 2)
7003 (5000, 2000, 2, 1)


The following will output false:

4
209
8889
4242424242
[ANYTHING ABOVE 8888]


# ALTERNATIVE TEST DATA (US Dollar)

coins = [1, 5, 10, 25, 50, 100, 200, 500, 1000, 2000, 5000, 10000]


Good luck!

• I wish we have more newcomers like you... May 8, 2017 at 17:41
• Related May 8, 2017 at 17:55
• You should add some testcases using a different set of coin May 8, 2017 at 18:18
• I'd suggest adding test cases that cannot be solved with the greedy heuristic of taking the largest unused coin that is that is at most the remaining value. It would also be good to have ones where the input isn't sorted and where a value can be made more than one way. It's generally good for test cases to avoid the possibility that someone makes a reasonable attempt at the problem that works for the test cases without being right on everything.
– xnor
May 8, 2017 at 20:17
• Related. Also related. The former question is arguably a duplicate, but this question is IMO better-designed and if we're to close one as a duplicate, I'd rather close the older one.
– user62131
May 8, 2017 at 21:24

# Brachylog 2 (TIO Nexus), 2 bytes

⊇+


Try it online!

Takes the list of coins either via standard input or via prepending it to the start of the program as an array literal (either will work, so it's up to you as to which you feel is "more legitimate"; the former is allowed by default PPCG rules, the latter specifically allowed by the question); and takes the value to produce as a command-line argument.

## Explanation

This program makes use of implementation details of the way TIO Nexus's wrapper for Brachylog functions; specifically, it lets you give a command-line argument to give input via the Output. (This wasn't envisaged in the original design for Brachylog; however, languages are defined by their implementation on PPCG, and if an implementation comes along that happens to do what I need, I can therefore take advantage of it.) That means the program looks like this:

⊇+
⊇   Some subset of {standard input}
+  sums to {the first command-line argument}


As a full program, it returns a boolean value; true. if all the assertions in the program can be simultaneously satisfied, or false. if they can't be.

(A reminder, or for people who don't already know: Brachylog 2 uses its own character encoding in which ⊇ is a single byte long.)

• You said that ⊇ is a single byte in Brachylog, why don't you paste the bytes here? I bet there's a reason for it, I'm just interested, bit of a character-encoding nub. May 9, 2017 at 7:07
• They're encoded on disk as 08 2B (you can look the encodings up here). The reason I didn't list the specific encoding is that it's irrelevant; all that really matters is that Brachylog uses no more than 256 unique characters, so that each can be represented in a single byte. This is commonly done by golfing languages to make the code more readable; they could use an encoding like code page 437 instead, but if you did that nobody would be able to read it.
– user62131
May 9, 2017 at 7:10

# 05AB1E, 4 bytes

æOså


Explanation:

æ      Calculate the powerset of the first input
O     Sum each element
s    Put the second input at the top of the stack
å   Check whether the input is in the powerset sum.


Try it online!

• Looks like you have officially misled everyone into compressing the list ;p May 8, 2017 at 18:16
• Once you have deleted your compressed list and moved it to the input, I'll delete my answer (because by the time our answers would be the same) May 8, 2017 at 18:19
• This community is full of geniuses.
– Tobi
May 8, 2017 at 19:40

# Mathematica, 25 bytes

!FreeQ[Tr/@Subsets@#,#2]&


Pure function taking an array of coin-values as the first argument and the target integer as the second argument, and returning True or False.

# Jelly, 6 bytes

ŒPS€e@


Try it online!

• including you May 8, 2017 at 18:17
• @LeakyNun Heh, there's a better solution, isn't there. May 8, 2017 at 18:17
• @JonathanAllan Oh, whoops. Thanks! May 8, 2017 at 18:54
– Okx
May 8, 2017 at 19:10

The operator function (#) takes an integer and a list of integers (or, more generally, any Traversable container of numbers) and returns a Bool.

Use as 6#[1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000].

c#l=elem c$sum<$>mapM(:)l


Try it online!

# How it works

• c is the desired value and l the list of coin values.
• mapM(:)l maps (:) over l, pairing each value with 0, and then constructs the cartesian product, giving lists where each element is either its corresponding value in l, or 0.
• sum<$> sums each combination, and elem c$ checks if c is in the resulting list.

# Retina, 52 31 bytes

\d+
$* ^((1+) |1+ )+(?<-2>\2)+$


Try it online! Takes input as a space-separated list of coins and notes followed by the desired value. Edit: Saved 18 bytes thanks to @Kobi who debugged my code. Explanation: The first two lines simply convert from decimal to unary. The third line then captures the list of coins and notes. The alternation allows the engine to backtrack and choose not to capture specific coins/notes. The balancing group then matches the value against all suffixes of the the capture list (unnecessary but golfier.)

• The second option doesn't work because the engine doesn't backtrack into 0-length groups (an annoying optimization). You could use ^((1+) )+(\2?(?<-2>)|){99}$ (34 bytes, with limit on number of coins), or ^((1+) |1+ )+(\2?(?<-2>))+$ (also 34 bytes).
– Kobi
May 9, 2017 at 5:08
• @Kobi Beautiful! I saved 2 bytes from both answers because I forgot that (?<-2>\2?) works, plus a further byte from your second answer because the ? is no longer necessary.
– Neil
May 9, 2017 at 8:58

# Brachylog, 7 bytes

tT&h⊇+T


Try it online!

## How it works

tT&h⊇+T
tT      the second input is T
&     and
h    the first input
⊇   is a superset of a set
+  that sums up to
T T


## Including the combination, 9 bytes

tT&h⊇.+T∧


Try it online!

# Java (OpenJDK 8), 125 bytes

boolean f(int[]c,int n){int l=c.length;if(l<1)return n==0;int[]a=java.util.Arrays.copyOf(c,l-1);return f(a,n-c[l-1])|f(a,n);}


Try it online!

• Doing this in a lambda could make it shorter.
– Okx
May 8, 2017 at 19:11
• @Okx It is recursive (so it would be longer), plus I don't do lambdas even if they would be shorter. May 8, 2017 at 19:14
• The iterative version of your algorithm is way shorter as you remove the need to copy the array: boolean f(int[]c,int n){for(int l=c.length;l-->0;n-=n<c[l]?0:c[l]);return n<1;} (79 bytes). With Java 8 and its lambdas, it can further be reduced to 62 bytes. Regarding your answer as it currently is, int l=c.length-1 then using l instead of l-1 is also shorter. May 9, 2017 at 13:30

# Prolog (SWI), 46 bytes

a([],0).
a([H|T],X):-Y is X-H,(a(T,Y);a(T,X)).


Try it online!

• You can probably save 2 bytes by using GNU Prolog instead (allowing you to spell is as #=, which would let you remove some whitespace).
– user62131
May 8, 2017 at 22:46

## JavaScript (ES6), 816967 64 bytes

Takes the list of coins c and the target amount a in currying syntax (c)(a). Returns 0 or true.

c=>g=(a,m=1)=>c.map((c,i)=>x-=c*(m>>i&1),x=a)&&!x||x-a&&g(a,m+1)


### Test cases

let f =

c=>g=(a,m=1)=>c.map((c,i)=>x-=c*(m>>i&1),x=a)&&!x||x-a&&g(a,m+1)

const pound = [1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000];

console.log(f(pound)(6))
console.log(f(pound)(15))
console.log(f(pound)(88))
console.log(f(pound)(512))
console.log(f(pound)(7003))

console.log(f(pound)(4))
console.log(f(pound)(209))
console.log(f(pound)(8889))
console.log(f(pound)(4242424242))

• Are you allowed to take the list of coins? May 8, 2017 at 18:12
• @LeakyNun "... and can take a list of coin/note values ..." May 8, 2017 at 18:15
• So I encoded the list for nothing... May 8, 2017 at 18:16
• @LeakyNun It seems so
– User
May 8, 2017 at 19:09

# R, 88 83 bytes

-5 bytes thanks to @Jarko Dubbeldam

returns an anonymous function. It generates all the possible combinations of coins (using expand.grid on pairs of T,F) and checks if the value(s) are present. k is coins since c is a reserved word in R. Can check multiple values at once.

function(k,v)v%in%apply(expand.grid(Map(function(x)!0:1,k)),1,function(x)sum(k[x]))


Try it online!

• You can replace c(T,F) by !0:1, and rep(list(!0:1),length(k)) by lapply(k,function(x)!0:1)
May 10, 2017 at 10:54
• Actually, make that Map(function(x)!0:1,k)
May 10, 2017 at 11:02

# Jelly, 4 bytes

ŒP§i


Try it online!

Powerset, vector sum, index.

Powerset gets all subsets, sum all the subsets, and check for the occurrence of the second argument

Returns 0 as the falsy value, and anything else otherwise.

# Japt, 7 bytes

à mx èN


Try it online! Outputs 0 for falsy, a positive integer for truthy.

### Explanation

à mx èN
// Implicit: U = input array, V = input integer, N = array of all inputs
à         // Take all combinations of U.
mx      // Map each combination to its sum.
è    // Count the number of items in the result which also exist in
N   //   the array of inputs.
// This returns 0 if no combination sums to V, a positive integer otherwise.
// Implicit: output result of last expression


# Python 3, 52 bytes

5 bytes thanks to ovs.

f=lambda c,n:c and f(c[1:],n-c)|f(c[1:],n)or n==0


Try it online!

# Ruby, 39 bytes

Returns nil as the falsy value, and the smallest coin value in the list that makes up the number as truthy (all numbers are truthy in Ruby).

f=->c,n{n!=0?c.find{|i|f[c-[i],n-i]}:1}


Do beware, however, that this algorithm is insanely slow, with O(C!) time complexity, where C is the length of the coin list. It eventually finishes, but most test cases will time out on most online interpreters, even f(UK_POUND, 5).

Here is a 41-byte version that finishes much faster by adding an extra ending condition, and is much harder to actually time out

f=->c,n{n>0?c.find{|i|f[c-[i],n-i]}:n==0}


Try it online!

# Bash + GNU utilities, 56 39

printf %$2s|egrep "^ {${1//,/\}? {}}?$"  Input denomination list (unsorted) is given as a comma-separated list. Input list and value are given as a command-line parameters. Output given in the form of the shell return code. Inspect with echo$? after running the script. 0 means truthy, 1 means falsy.

• printf %$2s outputs a string of value spaces • "^ {${1//,/\}? {}}?$" is a shell expansion that expands the denomination list to a regex like ^ {1}? {2}? {5}? {10}? ...$. It turns out that the egrep regex engine is smart enough to correctly match with this, regardless of what order the denominations are in
• egrep checks if the string of spaces matches the regex

## C, 66 bytes

m;v;f(n){for(m=1e5;m/=10;)for(v=5;n-=n<v*m?0:v*m,v/=2;);return!n;}


See it work here.

## C, 53 bytes

g(c,w,n)int*c;{for(;n-=n<c[--w]?0:c[w],w;);return!n;}


This variant takes the coin array, which defeats the purpose of this problem, because it comes down to simple subtraction.

The first argument is the coin array, the second is the coin count, and the third is the value.

## C, 48 bytes

g(c,n)int*c;{for(;n-=n<*c?0:*c,*++c;);return!n;}


An alternative to the previous variant. It assumes that the coin array can be reversed and zero terminated.

# Pyth, 6 bytes

/sMtyE


Test suite.

# CJam, 18 17 bytes

q~_,2\m*\f.*::+#)


Try it online!

Explanation

q~                  e# Read and eval input.
_,                e# Duplicate the money list and take its length.
2\m*            e# Take the (length)th Cartesian power of [0 1].
\f.*        e# Element-wise multiplication of each set of 0's and 1's with the money
e#   list. This is essentially the powerset, but with 0s instead of
e#   missing elements.
::+     e# Sum each set.
#    e# Find the index of the desired amount in the list. (-1 if not found)
)   e# Increment. -1 => 0 (falsy), anything else => nonzero (truthy)


# C (gcc), 91 bytes

i,j,c[]={1,2,5};f(n){for(i=1000;i;i/=10)for(j=2;j>=0;j--)n-=n<i*c[j]?0:i*c[j];return n==0;}


Try it online!

# PHP, 70 Bytes

prints 1 for true and nothing for false

<?foreach($_GETas$v)$i-=$v*$r[]=($i=&$_GET)/$v^0;echo max(\$r)<2;


Try it online!

# Octave, 39 bytes

 @(L,n)any(cellfun(@sum,powerset(L))==n)


An anonymous function that takes an array of coin-values as the first argument and the target integer as the second argument, and returns true or false.

Try it online!

# Mathematica, 42 bytes

ListQ@NumberDecompose[#,Sort[#2,Greater]]&


input

[15,{10,5}]