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

Question

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!

Answer 1

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

Answer 2

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!

Answer 3

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.

Answer 4

Jelly, 6 bytes

ŒPS€e@

Try it online!

-2 bytes thanks to Leaky Nun
-13 bytes thanks to Leaky Nun (long story)

Answer 5

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

Answer 6

JavaScript (ES6), 81 69 67 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))

Answer 7

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!

Answer 8

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!

Answer 9

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!

Answer 10

Prolog (SWI), 46 bytes

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

Try it online!

Fork of my Python answer.

Answer 11

Haskell, 28 bytes

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(:[0])l

Try it online!

How it works

• c is the desired value and l the list of coin values.
• mapM(:[0])l maps (:[0]) 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.

Answer 12

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

Answer 13

Python 3, 52 bytes

5 bytes thanks to ovs.

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

Try it online!

Answer 14

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.

Try it online.

• 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

Answer 15

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!

Answer 16

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.

Answer 17

Pyth, 6 bytes

/sMtyE

Test suite.

Answer 18

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)

Answer 19

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!

Answer 20

PHP, 70 Bytes

prints 1 for true and nothing for false

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

Try it online!

Answer 21

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!

Answer 22

Mathematica, 42 bytes

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

input

[15,{10,5}]