[Question]
  [
The [Cashier's Algorithm](https://en.wikipedia.org/wiki/Greedy_algorithm) is an algorithm for making change in the minimal number of coins that works quite well for most currency systems. However like most greedy algorithms it is not without its flaws. If a currency system is set up just right (or just wrong) there are certain values in which the Cashier's Algorithm will fail to find the optimal change.
Take the following example:
We have 4¢, 3¢, and 1¢ coins. We want to make 6¢.
The Cashier's Algorithm will first select as many of the largest coin (one 4¢ to start) and subtract and repeat. This will result in one 4¢ coin and two 1¢ coins, for a total of 3 coins.
Unfortunately for the Algorithm there is a way to make 6¢ with only two coins (two 3¢ coins).
A system of change will be considered canonical iff for all integer values the Cashier's Algorithm will find the optimal number of coins.
## Task
You task will be to take a system as a either an unordered container or sorted ordered container of integers representing coin values and output a truthy value if the system input is canonical and falsy otherwise.
Your program should work for all systems that can create any value. (i.e. all systems will have a 1¢ coin)
This is code golf least bytes wins.
## Test cases
*This list is by no means exhaustive, your program should work for all valid input*
```
1, 3, 4       -> 0
1, 5, 10, 25  -> 1
1, 6, 10, 25  -> 0
1, 2, 3       -> 1
1, 8, 17, 30  -> 0
1, 3, 8, 12   -> 0
1, 2, 8, 13   -> 0
1, 2, 4, 6, 8 -> 1
```
  
[Answer]
# Haskell, ~~94~~ ~~87~~ 82 bytes
```
f s=and[j i-2<j(i-x)|let j i=last$0:[1+j(i-x)|x<-s,x<i],i<-[1..2*last s],x<-s,x<i]
```
this solution works by defining a function `j` which perform's the cashier's algorithm and tells us how many coins the cashier used. we then check up to twice the biggest number in the list, assuming that the system has been canonical for all previous numbers, that taking the biggest possible coin is the right choice.
this solution assumes the input is sorted.
proof checking up to twice the biggest number is enough:
assume that the system is not canonical for some number `i`, and let `k` be the biggest number in the list not bigger than `i`. assume that `i >= 2k` and the system is canonical for all numbers less than `i`.
take some optimal way to make `i` out of coins, and assume it doesn't contain the coin `k`. if we throw away one of the coins, the new sum of coins must be bigger than `k` and smaller than `i` - but the cashier's algorithm on this number would use the `k` coin - and therefore, this set of coins can be replaced with an equal set of coins containing the coin `k`, and therefore there is a set of coins containing the coin `k` for the number `i`, and by induction the cashier's algorithm returns the optimal choice.
this argument really shows that we only need to check until the sum of the two biggest elements - but it is lengthier to do so.
Edit: five bytes off thanks to Ørjan Johansen!
[Answer]
# Pyth, ~~18~~ 15 bytes
```
!x#eST.gsky_S*e
```
[Test suite](https://pyth.herokuapp.com/?code=%21fxlDTeST.gsky_S%2ae&input=1%2C+8%2C+17%2C+30&test_suite=1&test_suite_input=1%2C+2%2C+3%0A1%2C+2%2C+4%0A1%2C+3%2C+4&debug=0)
A different sort of brute force. This starts by forming all collections of coins with up to k of each, where k is the largest coin, which is assumed to be the last coin. I believe this always sufficient to form two sets of coins with the same sum, one greedy and one shorter, whenever such a pair exists.
I then locate such a pair as follows:
The subsets are generated in order of increasing size, and lexicographically by position in the input secondarily. Group the coin collections by their sums, stably. Each coin collection is generated in descending order, so the greedy solution will be the first element of the group if and only if the greedy solution is optimal, and it will be the last element of the group lexicographically. Thus, we find the greedy solution, and filter on a nonzero index in the group. If the coin set is cannonical, this will filter out everything, so we simply logically negate the result and output.
Explanation:
```
!x#eST.gsky_S*e
!x#eST.gsky_S*eQQ   Variable introduction.
                    Q = eval(input()) - sorted list of coins.
              eQ    Greatest coin in the list
             *  Q   Repeat that many times.
            S       Sort the coins
           _        Reverse, so we have the coins in descending order.
          y         Form all subsets, in increasing size then
                    decreasing lexicographic order.
      .gsk          Group by sum
 x#                 Filter by the index in the group of
   eST              The last element lexicographically (greedy solution).
!                   Logically negate.
```
[Answer]
# PHP, 323 Bytes
Same way as other count the coins until the sum of the two last elements in the array
```
<?function t($g){rsort($g);$m=array_slice($g,1);for($y=1,$i=$g[0];$i<$g[0]+$m[0];$i++){$a=$b=$i;$p=0;$r=$s=[];while($a||$b){$o=$n=0;$g[$p]<=$a?$a-=$r[]=$g[$p]:$o=1;($m[$p]??1)<=$b?$b-=$s[]=$m[$p]:$n=1;$p+=$o*$n;}$y*=count($r)<=count($s);}return$y;}for($i=0,$t=1;++$i<count($a=$_GET[a]);)$t*=t(array_slice($a,0,$i+1));echo$t;
```
# My best and longest answer I believe >370 Bytes
I give only an expanded version cause it is longer then my answer before
```
for($x=1,$n=0,$f=[];++$n<count($a)-1;){
$z=array_slice($a,0,$n+1);
$q=$a[$n]-$a[$n-1];
$i=array_fill(1,$c=max($a[$n+1]??1,11),"X");#$q*$a[$n]
$f=range($a[$n],$c,$q);
$f[]=2*$a[$n];
for($d=[$z[$n]],$j=0;$j<$n;){
   $f[]=$a[$n]+$d[]=$z[$n]-$z[$j++]; 
}
while($f){
    $i[$t=array_pop($f)]="T";
    foreach($d as $g)
    if(($l=$t+$g)<=$c)$f[]=$l;
}
foreach($i as$k=>$v){
    if(in_array($k,$z))$i[$k]="S";
}
#var_dump($i);
if($i[$a[$n+1]]=="X")$x*=0;
}
echo$x;
```
## Explanation for this answer
[Online Version](http://sandbox.onlinephpfunctions.com/code/331bdc6675c34841bd322ec1adb0cd75dfd2eeb5)
1. Set all in the array to false == X
2. Set all numbers in the array you control to S
3. Found differences between the last S and the other S or 0
4. Start at last S in the array
5. Set all number to D Where Last S+ one of all differences
6. Begin at all D
7. SET "T" to D values in the array
8. GOTO 5 Repeat it with all found D I did it not really in the code
9. If next item in the Array has X it is a false case else True
Additional Steps 
Difference is in the case in the snippet 3
Between 1 and 4 are 2 X 
This means you need the second D by Step 5. After this value in this case 10 are all cases true
I could see so far that there is a relationship between difference and the count in the array you control to calculate how much D (Step 5) you need to get the point before you find the last false case.
You set multiple values from the last item directly to true. 
These Points can make a difference to decide if it could been that the greedy count of coins with the next value is same then the multiple of the last in the array.
On the other way you can set enemy 
1. Set first enemy at 1+Last S
2. From this Point add each value in the array to set the next enemies
3. Start with last enemy Goto 2
If you now have enemies and true cases in it the 
probability grows that the counts can be the same 
With more D the probability sinks.
```
table{width:80%}
td,th{width:45%;border:1px solid blue;}
```
```
<table>
  <caption>Working [1,4]</caption>
<tr><th>Number</th><th>Status</th></tr>
<tr><td>1</td><td>S</td></tr>
<tr><td>2</td><td>X</td></tr>
<tr><td>3</td><td>X</td></tr>
<tr><td>4</td><td>S</td></tr>
<tr><td>5</td><td>X</td></tr>
<tr><td>6</td><td>X</td></tr>
<tr><td>7</td><td>D3</td></tr>
<tr><td>8</td><td>D4</td></tr>
<tr><td>9</td><td>X</td></tr>
<tr><td>10</td><td>D3D3</td></tr>
<tr><td>11</td><td>D4D3</td></tr>
<tr><td>12</td><td>D4D4</td></tr>
<tr><td>13</td><td>D3D3D3</td></tr>
<tr><td>14</td><td>D4D3D3</td></tr>
<tr><td>15</td><td>D4D4D4</td></tr>
<tr><td>16</td><td>D4D4D3</td></tr>
</table>
<ul>
  <li>S Number in Array</li>
  <li>D Start|End point TRUE sum Differences from last S</li>
  <li>X False</li>
  </ul>
```
plus ? Bytes Thank You @JonathanAllan to give me wrong test cases  
262 Bytes
Nearly but not good enough 4 wrong testcase in the moment
[test cases](http://sandbox.onlinephpfunctions.com/code/bb1b7985dec56dfc788bf54ce2e99e550b45e892) [1,16,256] before should true after false
```
<?for($q=[1],$i=0,$t=1,$w=[0,1];++$i<count($a=$_GET[v]);$w[]=$a[$i],$q[]=$m)($x=$a[$i]-$a[$i-1])>=($y=$a[$i-1]-$a[$i-2])&&((($x)%2)==(($m=(($a[$i]+$x)*$a[$i-1])%$a[$i])%2)&&$m>array_sum($q)||(($x)%2)==0&&(($a[$i]-$a[$i-2])*2%$y)==0||in_array($m,$w))?:$t=0;echo$t;
```
Ascending Order of the Array
## Explanation
```
for($q=[1],$i=0,$t=1,$w=[0,1] # $t true case $q array for modulos $w checke values in the array
;++$i<count($a=$_GET[v])   #before loop
;$w[]=$a[$i],$q[]=$m) # after loop $q get the modulo from the result and fill $w with the checked value
($x=$a[$i]-$a[$i-1])>=($y=$a[$i-1]-$a[$i-2]) 
# First condition difference between $a[i] and $a[$i-1] is greater or equal $a[$i-1] and $a[$i-2]
# if $a[$-1] == 1 $a[$i-2] will be interpreted as 0
&&  ## AND Operator with the second condition
(
(($x)%2)==   # See if the difference is even or odd
(($m=(($a[$i]+$x)*$a[$i-1])%$a[$i])%2)&&$m>array_sum($q)
# After that we multiply the result with the lower value *$a[$i-1]
    # for this result we calculate the modulo of the result with the greater value %$a[$i]
    # if the difference and the modulo are both even or odd this belongs to true
# and the modulo of the result must be greater as the sum of these before
    # Ask me not why I have make try and error in an excel sheet till I see this relation
||
(($x)%2)==0&&(($a[$i]-$a[$i-2])*2%$y)==0 # or differce modulator is even and difference $a[$i],$a[$i-1] is a multiple of half difference $a[$i-1],$a[$i-2] 
||
in_array($m,$w) # if the modulo result is equal to the values that we have check till this moment in the array we can also neglect the comparison
)
?:$t=0; # other cases belongs to false
echo$t; #Output
```
It looks like that what I have seen
the table contains values from [1,2,3,4,5,6] and I change only the last item until 9. for 2to3 and 4to5 we create the value of the lower value in the modulo calculation
```
table{width:95%;}th,td{border:1px solid}
```
```
<table><tr><th>difference</th><td></td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr>
<tr><th>difference modulo 2</th><td></td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr>
<tr><th>value</th><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td></tr>
<tr><th>result</th><td></td><td>3</td><td>8</td><td>15</td><td>24</td><td>35</td></tr>
<tr><th>modulo value great</th><td></td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td></tr>
<tr><th>modulo 2</th><td></td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td></tr>
<tr><th></th><td></td><td></td><td></td><td></td><td></td><td></td></tr>
<tr><th>difference</th><td></td><td>1</td><td>1</td><td>1</td><td>1</td><td>2</td></tr>
<tr><th>difference modulo 2</th><td></td><td>1</td><td>1</td><td>1</td><td>1</td><td>0</td></tr>
<tr><th>value</th><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>7</td></tr>
<tr><th>result</th><td></td><td>3</td><td>8</td><td>15</td><td>24</td><td>45</td></tr>
<tr><th>modulo value great</th><td></td><td>1</td><td>2</td><td>3</td><td>4</td><td>3</td></tr>
<tr><th>modulo 2</th><td></td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td></tr>
<tr><th></th><td></td><td></td><td></td><td></td><td></td><td></td></tr>
<tr><th>difference</th><td></td><td>1</td><td>1</td><td>1</td><td>1</td><td>3</td></tr>
<tr><th>difference modulo 2</th><td></td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr>
<tr><th>value</th><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>8</td></tr>
<tr><th>result</th><td></td><td>3</td><td>8</td><td>15</td><td>24</td><td>55</td></tr>
<tr><th>modulo value great</th><td></td><td>1</td><td>2</td><td>3</td><td>4</td><td>7</td></tr>
<tr><th>modulo 2</th><td></td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td></tr>
<tr><th></th><td></td><td></td><td></td><td></td><td></td><td></td></tr>
<tr><th>difference</th><td></td><td>1</td><td>1</td><td>1</td><td>1</td><td>4</td></tr>
<tr><th>difference modulo 2</th><td></td><td>1</td><td>1</td><td>1</td><td>1</td><td>0</td></tr>
<tr><th>value</th><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>9</td></tr>
<tr><th>result</th><td></td><td>3</td><td>8</td><td>15</td><td>24</td><td>65</td></tr>
<tr><th>modulo value great</th><td></td><td>1</td><td>2</td><td>3</td><td>4</td><td>2</td></tr>
<tr><th>modulo 2</th><td></td><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td></tr></table>
```
[Answer]
# JavaScript (ES6), 116 ~~125 130~~
```
l=>eval("r=(d,k)=>d?--k&&l.map(v=>v>d||r(d-v,k)):x=1;for(x=l[0]*2;--x>1;r(x,g))g=0,h=x,l.map(v=>(g+=h/v|0,h%=v));x")
```
This needs the input array sorted in descending order. For each value from 2N downto 2 (N being the max coin value), it find the number of coins from the greedy algorithm and try to find a smaller set of coins.
*Less golfed*
```
l=>{
  // recursive function to to find a smaller set of coins
  // parameter k is the max coin limit
  r = (d,k) => d // check if difference is not 0
     ? --k // if not, and if the number of coins used will be less than limit
      && l.map(v => v>d || r(d-v, k))  // proceed with the recursive search
     : x=1 // if diff is 0, value found, set x to 1 to stop the loop
  for( x=l[0]*2; --x > 1; )  
    g=0, h=x, l.map(v=>(g += h/v|0, h %= v)), // find g with the greedy algorithm
    r(x,g) // call with initial difference equal to target value
  return x
}
```
**Test**
```
f=
l=>eval("r=(d,k)=>d?--k&&l.map(v=>v>d||r(d-v,k)):x=1;for(x=l[0]*2;--x>1;r(x,g))g=0,h=x,l.map(v=>(g+=h/v|0,h%=v));x")
/* No eval
f=l=>{
  r=(d,k)=>d?--k&&l.map(v=>v>d||r(d-v,k)):x=1;
  for(x=l[0]*2;--x>1;r(x,g))
    g=0,h=x,l.map(v=>(g+=h/v|0,h%=v));
  return x;
}*/
;[
 [[100,50,20,10,5,2,1],1], [[4,3,1],0],
 [[25,10,5,1],1], [[25,10,6,1],0],
 [[3,2,1],1], [[30,17,8,1], 0], 
 [[12,8,3,1],0], [[13,8,2,1], 0]
].forEach(t=>{
  var i=t[0],k=t[1],r=f(i),
      msg=((r==k)?'OK ':'KO ')+i+' -> '+r
      + (r==k?'':' (should be '+k+')')
  O.textContent += msg+'\n'
})
function test()
{
  var i=I.value.match(/\d+/g).map(x=>+x).sort((a,b)=>b-a)
  O.textContent = i+' -> '+f(i)+'\n'+O.textContent
 }
```
```
#I { width:50% }
```
```
<input id=I value='1 4 9'><button onclick='test()'>test</button>
<pre id=O></pre>
```
[Answer]
# Python, ~~218 211~~ 205 bytes
-1 byte thanks to @TuukkaX (a space could be deleted between `<3` and `or`)
```
from itertools import*
g=lambda x,c,n=0:x and g(x-[v for v in c if v<=x][0],c,n+1)or n
lambda c:len(c)<3or 1-any(any(any(x==sum(p)for p in combinations(c*i,i))for i in range(g(x,c)))for x in range(c[0]*2))
```
**[repl.it](https://repl.it/DvoH/4)**
Input in descending order.
Horribly brute force. Any set of a single unit coin and some other coin is canonical. For larger sets the smallest fail case, if one exists will be greater than or equal to the 3rd smallest coin (not sure myself how it could be equal!) and less than the sum of the two largest coins - see [this paper](https://ecommons.cornell.edu/bitstream/handle/1813/6219/94-1433.pdf?sequence=1&isAllowed=y) (which actually references another but also gives an O(n^3) method).
`g` counts the coins used by the greedy method, and the unnamed function traverses the possible candidates (actually from 0 to one less than twice the largest coin to save bytes) and looks for any collection of less coins that also sum to that amount.
`g` works by performing what a cashier would, it recursively takes the largest coin less than or equal to the amount still to make up, `[v for v in c if v<=x][0]` away, and counts up the number of coins used, `n`.
The unnamed function returns 1 if `len(c)` is less than 3, and otherwise tests that it is not the case, `1-...`, that any values in the range of possibilities, `range(c[0]*2)))`, are possible with less coins, `i in range(g(x,c))`, by making a collection of that many of every coin, `c*i`, and examining all combinations of `i` coins, `combinations(c*i,i)`, to see if any sum to the same value.
[Answer]
# Jelly ([fork](https://github.com/miles-cg/jelly/tree/frobenius)), ~~15~~ 14 bytes
```
SRæFµS€Ṃ=$Ṫµ€Ȧ
```
This solution uses the bounds for counter-examples from this [paper](https://arxiv.org/PS_cache/arxiv/pdf/0809/0809.0400v1.pdf). There, the author uses a tight bound for the counter-example, but in the interests of golfing, the range of the sum of coin denominations is used which is larger and contains that bound.
This program computes all test cases in less than a second on my machine.
Unfortunately, this relies on a [branch](https://github.com/miles-cg/jelly/tree/frobenius) of Jelly where I was working on implementing a Frobenius solve atom so you cannot try it online.
## Usage
```
$ ./jelly eun 'SRæFµS€Ṃ=$Ṫµ€Ȧ' '1,2,4,6,8'
1
```
The performance is good and can solve all test cases at once in less than a second.
```
$ time ./jelly eun 'SRæFµS€Ṃ=$Ṫµ€Ȧ¶Ç€' '[[1,3,4],[1,5,10,25],[1,6,10,25],[1,2,3],[1,8,17,30],[1,3,8,12],[1,2,8,13],[1,2,4,6,8]]'
[0, 1, 0, 1, 0, 0, 0, 1]
real    0m0.793s
user    0m0.748s
sys     0m0.045s
```
# Explanation
```
SRæFµS€Ṃ=$Ṫµ€Ȧ  Input: list of integers C
    µ           Start a new monadic chain
S                 Sum
 R                Range, [1, 2, ..., sum(C)]
  æF              Frobenius solve for each X in the range using coefficients from C
                  This generates all vectors where the dot product of a
                  vector with C equals X, ordered by using values from the
                  start to end of C
           µ€   Start a new monadic chain that operates on each list of vectors
     S€           Sum each vector
         $        Monadic hook on the sums
       Ṃ            Minimum (This is the optimal solution)
        =           Vectorized equals, 1 if true else 0
          Ṫ       Tail (This is at the index of the greedy solution)
             Ȧ  All, returns 0 if it contains a falsey value, else 1
```
[Answer]
## JavaScript (ES6), ~~144~~ ~~132~~ ~~124~~ ~~122~~ 110 bytes
```
a=>![...Array(a[0]*2)].some((_,i)=>(g=(a,l=0,n=i)=>[a.filter(c=>c>n||(l+=n/c|0,n%=c,0)),-l*!n])(...g(a))[1]>0)
```
Requires the array to be sorted in descending order. Uses the observation in the linked paper that if the system is not canonical then there is at least one value less than 2a[0] which takes fewer coins when decomposed using the unused coins from the initial greedy algorithm.
Edit: Saved 12 bytes by realising that I could check all the coins even though I had already reached the target value. Saved 8 bytes by switching my intermediate output from `[l,b]` to `[b,-l]`; this allowed me to pass the first result directly as the parameter of the second call, plus also a small saving detecting whether the second call was successful. Saved 2 bytes by moving the definition of `g` into the `some` callback, allowing me to avoid unnecessarily passing in the loop variable twice. Saved 12 bytes by switching from my recursive helper function to a call to `filter` (made possible by my intermediate output switch).
[Answer]
# Perl, 69 bytes
Includes +2 for `-pa`
Give coins in descending order on STDIN. You can optionally leave out the `1` coin.
```
coins.pl <<< "4 3 1"
```
`coins.pl`:
```
#!/usr/bin/perl -pa
$_=!map{grep$`>=$_&&($n=$G[$`-$_]+1)<($G[$`]||=$n),@F,/$/}1..2*"@F"
```
Builds up the number of coins used by the cashiers algorithm in `@G` for amounts 1 to twice the largest coin. For each amount checks that if that amount is reduced by 1 coin value the cashiers algorithm needs at most 1 less coin. If not this is a counterexample (or there was an earlier counterexample). I could stop at the first counterexample but that takes more bytes. So the time complexity is `O(max_coin * coins)` and space complexity is `O(max_coin)`
]