#include <iostream>
#include <iomanip>
#include <vector>

using namespace std;

class coinset: public vector<int>
{ public:

    coinset(initializer_list<int> values): vector<int>(values)
    { }

    coinset without_last()
    { coinset copy = * this;
      copy.pop_back();
      return copy; } };

ostream & operator<<(ostream & out, const coinset & coins)
{ if (coins.size() == 0)
  { out << " (none)";
    return out; }
  for (int c: coins)
    out << " " << c;
  return out; }

int numcoins(int amt, coinset coins)
{ if (amt == 0)
    return 0;
  if (coins.size() == 0)
    return 999999999;
  int coin = coins.back();
  int numwith = 999999999;
  if (coin <= amt)
    numwith = 1 + numcoins(amt - coin, coins);
  int numwithout = numcoins(amt, coins.without_last());
  return min(numwith, numwithout); }

void whichcoins(int amt, coinset coins)
{ if (amt == 0)
    return;
  if (coins.size() == 0)
    return;
  int coin = coins.back();
  if (coin > amt)
    whichcoins(amt, coins.without_last());
  else
  { int best = numcoins(amt, coins);
    int way1 = 1 + numcoins(amt - coin, coins);
    if (way1 == best)
    { cout << coin << " ";
      whichcoins(amt - coin, coins); }
    else
      whichcoins(amt, coins.without_last()); } }

int main()
{ coinset coins({ 1, 3, 6, 12, 24, 30 });
  while (true)
  { int amt;
    cout << "Amount to give change for: ";
    cin >> amt;
    if (cin.fail())
    { cout << "\n";
      break; }
    int num = numcoins(amt, coins);
    cout << "\n" << num << " coins will do it\n";
    whichcoins(amt, coins);
    cout << "\n\n"; } }