[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]
# [Brachylog](https://github.com/JCumin/Brachylog) 2 (TIO Nexus), 2 bytes
```
⊇+
```
[Try it online!](https://tio.run/nexus/brachylog2#@/@oq137//9oQx0FIx0FUx0FQwMgC4hNDUBsMAfMg3AhfIiAQex/U0MTAA "Brachylog – TIO Nexus")
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]
# [05AB1E](https://github.com/Adriandmen/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!](https://tio.run/nexus/05ab1e#@394mX/x4aX//0cb6igY6SiY6igYGgBZQGxqAGKDOWAehAvhQwQMYrnMDQyMAQ "05AB1E – TIO Nexus")
[Answer]
# 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]
# [Jelly](https://github.com/DennisMitchell/jelly), 6 bytes
```
ŒPS€e@
```
[Try it online!](https://tio.run/##y0rNyan8///opIDgR01rUh3@//8fbaijYKSjYKqjYGgAZAGxqQGIDeaAeRAuhA8RMIj9b2EBAA "Jelly – Try It Online")
[Answer]
# [Haskell](https://www.haskell.org/), 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!](https://tio.run/nexus/haskell#NYxNCoMwEEb3c4qgLpKqIbHaqqh7oaUHEBeioRWSWPyhx7dR2xkGvveYGdX0Ou8GJDN/FE1302laPqpSz@IpxhrQr3ojxqadnUXLXouJquaN8fQaPlN2KrCF/AJZrkvopii2JSF0@0fovr62tsyFFAq1zrSozCnM/R2nFauJXNeKeyjwUOQhzkwyE7Et77DTgQcfgtVwAR5BHEPEA7gydoYQApYYEycQBv8@@As "Haskell – TIO Nexus")
# 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]
# [Retina](https://github.com/m-ender/retina), ~~52~~ 31 bytes
```
\d+
$*
^((1+) |1+ )+(?<-2>\2)+$
```
[Try it online!](https://tio.run/nexus/retina#lc8xCoAwDIXhvafIUKE1CEm02oLo6CWKOHgM715tT2C2/8G3vM4dV8k3Gtub0zlGDw8jeHT7OsiWxaMthUEgABMIQaAvatVs3UZbBLP5bzkocIwKHFgUeiEaFXxSWKGk@hjTCw "Retina – TIO Nexus") 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]
# [Brachylog](https://github.com/JCumin/Brachylog), 7 bytes
```
tT&h⊇+T
```
[Try it online!](https://tio.run/nexus/brachylog2#@18SopbxqKtdO@T//@hoQx0jHVMdQwMdIwMdUwMgA8QCMcFsMAfMM4jVMTcwMI4FAA)
## 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!](https://tio.run/nexus/brachylog2#@18SopbxqKtdTzvkUcfy//@jow11jHRMdQwNdIwMdEwNgAwQC8QEs8EcMM8gVsfcwMA49n8UAA)
[Answer]
# [Java (OpenJDK 8)](http://openjdk.java.net/), 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!](https://tio.run/nexus/java-openjdk#lZBNbsMgEIXX8SlmCRJB4MatK9eLHqDqIssoC0Jtl4qAZXAqy/XZU7B7gCKE3rzRNz/QjxetJEgtnIM3ocx8v1irG2GgRcr401mSIGDwHEXXkurGdP6zUi3SLxwPjR8HA6auWbXyov4SN0FHrzR9HQYxOSptP723SBK957j6q2iRIGYvTyF3xj@rw9Vy77eFnBc@yM2qD7iGtdDRD8p0of3QOTxnu3UWSKuMgxpM8w1rZuYEcgIFAc5CFG7BYrya1W1281uCLVW2O07ON1dqR0/7MMlrg2LT@CUI07B8nEQeMf43y4sEuCwT4ILnCfQTYw8J@CGBzdlz0hvLFPyQbyeWLNly/wU "Java (OpenJDK 8) – TIO Nexus")
[Answer]
# [Prolog (SWI)](http://www.swi-prolog.org), 46 bytes
```
a([],0).
a([H|T],X):-Y is X-H,(a(T,Y);a(T,X)).
```
[Try it online!](https://tio.run/nexus/prolog-swi#@5@oER2rY6CpxwVkeNSExOpEaFrpRipkFitE6HroaCRqhOhEalqDqAhNTb3//4HKDHUUjHQUTHUUDA2ALCA2NQCxwRwwD8KF8CECBrE6CuYGBsaaegA "Prolog (SWI) – TIO Nexus")
Fork of [my Python answer](https://codegolf.stackexchange.com/a/119627/48934).
[Answer]
## 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]
# 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!](https://tio.run/nexus/r#TY1dCsIwEITfe4r4UMjCKElsNYoewROID6E/ElrTYG2pp6@1UZFll/mGnd3yOJadyx62cbxCT31sXWy8r5@8GLxx@ep6tzk/Gc9/ewMtxF6iIoLEn9t2N16dhwvRmDXWteywZBmXYAosBZNiUlOn4q1nmClg4GAIinpTd8XnwgYyhdZIpcJWiDUSKLED01pPM1Hfoqjk82OwEKfxBQ)
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 4 bytes
```
ŒP§i
```
[Try it online!](https://tio.run/##y0rNyan8///opIBDyzP///9vqKNgpKNgqqNgaABkAbGpAYgN5oB5EC6EDxEw@G9uYGAMAA "Jelly – 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.
[Answer]
# [Japt](https://github.com/ETHproductions/japt), 7 bytes
```
à mx èN
```
[Try it online!](https://tio.run/nexus/japt#@394gUJuhcLhFX7//0cb6igY6SiY6igYGgBZQGxqAGKDOWAehAvhQwQMYrksgAAA "Japt – TIO Nexus") 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]
# [Python 3](https://docs.python.org/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!](https://tio.run/nexus/python3#PY5BCoMwEEX3OcWnKwNjSWxTUyG9SMgijQiBGot1Zz27jQpdzPDfMDz@2pmX75@tR6DUBPjUoiuClY2jVAYrHP/@mQ8jkjFiDUNMHxhYSagIiiBFTnmU2PIOOx148HEQjnXZExET7I2kIq1JyayphbgQrtvvnaC1zlvKWsvKNQzvMaapOM0Lygfm5XTOlt5PRaTcb@tDkXPO2PoD "Python 3 – TIO Nexus")
[Answer]
# [Ruby](https://www.ruby-lang.org/), 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!](https://tio.run/nexus/ruby#@59mq2uXrJNXnWdnYJ@sl5aZl1Jdk1mTFp2sG50Zq5Onmxlba5Vna2tQ@79AIU0vOTEnRyG1LDFHIz21pFhTB4n9P9pQR8FIR8FUR8HQAMgCYlMDEBvMAfMgXAgfImAQy2VuYGAMAA "Ruby – TIO Nexus")
[Answer]
# 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](https://tio.run/nexus/bash#ndTRCoIwFAbg@57isNZNTDxbrtZF@SIRRK0SSkOlG/PZTSfFDCo2vTnH@en0HztmOZS6KPe7QkOSwmYE7UE4E0wyjkwgk9gWXdWVpjaN6RDm5G2wR/8NlxbCj1d9Q0rZCH9M0EKSC@L@TQvEmQeLPIzApYdSSvmwSLxOC/dU/qamHYTt5OzAnaAduhMcBu8iP8J3oZGnGy4Ct/@jfKm1GEaHzDzhvrusaPXaDsZTqM3lg06zqzUwgWk/UOgSggCouQFoy5tbnqTlESZUFA99yvUNyBYqWvEwZOGmjqGq65iSpuN6f86A0Pf2E6yBxt1kUt08AQ).
* `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]
## 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](https://tio.run/nexus/c-gcc#VU/RasMwDHzPV2iFQby2xE6bNp1r9iFdGSFxmB8sjzQ1YyGfvedMdtqxyfgkztydNVnpZZsiG1rXpVYJXUibKcElC4RXhcS1wqN/si/8mXDlM5VLJjvdXzt8QDlOBnuwlcEUvDMNsGRIgCrQTdVXpzMoGGAHKxAFQVkSFCIn3HO@obalm/NDfCtD2@bzofHAuYARZLSsHV76X@O32l1pVHAxX9q1aSSBQfaPOPEzcbM@Qtgrehhs9CfJOcjbfPzreyOXS9oo6OatQn10JCf7xWPzigv65D0qCkLcPXBMxukb3bqu6nf9Aw).
## 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]
# [Pyth](https://github.com/isaacg1/pyth), 6 bytes
```
/sMtyE
```
[Test suite.](http://pyth.herokuapp.com/?code=%2FsMtyE&test_suite=1&test_suite_input=6%0A%5B1%2C+2%2C+5%2C+10%2C+20%2C+50%2C+100%2C+200%2C+500%2C+1000%2C+2000%2C+5000%5D%0A15%0A%5B1%2C+2%2C+5%2C+10%2C+20%2C+50%2C+100%2C+200%2C+500%2C+1000%2C+2000%2C+5000%5D%0A88%0A%5B1%2C+2%2C+5%2C+10%2C+20%2C+50%2C+100%2C+200%2C+500%2C+1000%2C+2000%2C+5000%5D%0A512%0A%5B1%2C+2%2C+5%2C+10%2C+20%2C+50%2C+100%2C+200%2C+500%2C+1000%2C+2000%2C+5000%5D%0A7003%0A%5B1%2C+2%2C+5%2C+10%2C+20%2C+50%2C+100%2C+200%2C+500%2C+1000%2C+2000%2C+5000%5D%0A4%0A%5B1%2C+2%2C+5%2C+10%2C+20%2C+50%2C+100%2C+200%2C+500%2C+1000%2C+2000%2C+5000%5D%0A209%0A%5B1%2C+2%2C+5%2C+10%2C+20%2C+50%2C+100%2C+200%2C+500%2C+1000%2C+2000%2C+5000%5D%0A8889%0A%5B1%2C+2%2C+5%2C+10%2C+20%2C+50%2C+100%2C+200%2C+500%2C+1000%2C+2000%2C+5000%5D%0A4242424242%0A%5B1%2C+2%2C+5%2C+10%2C+20%2C+50%2C+100%2C+200%2C+500%2C+1000%2C+2000%2C+5000%5D&debug=0&input_size=2)
[Answer]
# [CJam](https://sourceforge.net/p/cjam), ~~18~~ 17 bytes
```
q~_,2\m*\f.*::+#)
```
[Try it online!](https://tio.run/nexus/cjam#@19YF69jFJOrFZOmp2Vlpa2s@f@/oalCtKGCkYKpgqGBgpGBgqkBkAFigZhgNpgD5hnEAgA "CJam – TIO Nexus")
**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]
# [C (gcc)](https://gcc.gnu.org/), 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!](https://tio.run/nexus/c-gcc#fc3BDoIwDAbgO09BSEw2s8WxgEHn9EGQA5lMt0AxE0@Ex/bqhBhvYHv5069NvSGWqLyQfUw4SQehEeBetw4ZGTPGhBFmMyY8jazkwh4lE5ZSDFTCwaxVbosT23@DcFX3dBCCHJcG35QGEA76IBzr7gx0GkWryxkiEmq0xVjMS5wuUpYtUhrzyeYxWTzjbPfnW7aMCf/1tDIE/q10XV4fntbNC1qqSnWrPg "C (gcc) – TIO Nexus")
[Answer]
# 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!](https://tio.run/nexus/php#s7EvyCjgUol3dw2xjTY1NNKJNjUwMNAxAhGGIMIUwgNxgGwgE8jSMdUx0jGMjbX@n5ZflJqYnKEBNiDaMDaxWKVMUyVT11alTEulKDrWVkMl01YNImsQq6mvUhZnYJ2anJGvkJtYoaFSpGljZP3/PwA "PHP – TIO Nexus")
[Answer]
# 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!](https://tio.run/nexus/octave#dY4xC4MwEIX3/IqHUwIZom00IoJTJ8duxUE0gmCjeErpr7dR6ejBwfsO7uNtBS@lE7X78sYOQ7c6XtD6ltP4sTPZhZdC5LkTW5ejdpSxZuwdIccrlIgktESofPKr1Z4POOjEk8@DqjLG2p4mHjzn1WKxtKCpyVIgGOvGGW43xwg1YAygwwiJUreKwc/x2fGjge8smHXt3/eoB7oU3n2F1AtNijjWsTHJtXD7AQ "Octave – TIO Nexus")
[Answer]
# Mathematica, 42 bytes
```
ListQ@NumberDecompose[#,Sort[#2,Greater]]&
```
**input**
> 
> [15,{10,5}]
> 
> 
> 
]