title: Why does the greedy coin change algorithm not work for some coin sets?
body: <p>I understand how the greedy algorithm for the coin change problem (pay a specific amount with the minimal possible number of coins) works - it always selects the coin with the largest denomination not exceeding the remaining sum - and that it always finds the correct solution for specific coin sets.</p>
  
  <p>But for some coin sets, there are sums for which the greedy algorithm fails. For example, for the set <code>{1, 15, 25}</code> and the sum 30, the greedy algorithm first chooses 25, leaving a remainder of 5, and then five 1s for a total of six coins. But the solution with the minimal number of coins is to choose 15 twice.</p>
  
  <p>What conditions must a set of coins fulfil so that the greedy algorithm finds the minimal solution for all sums?</p>