In response to https://medium.com/p/1876e879651d/

change.cpp

#include <optional>
#include <unordered_set>
#include <vector>
#include <iostream>
#include <chrono>
#include <ctime>

template<typename T> std::optional<int> minimum_coins(T target, std::vector<T> denominations) {
  auto values = new std::unordered_set<T>(); values->insert(target);
  auto k = 0;
  while (values->size() > 0) {
    k += 1;
    auto newvalues = new std::unordered_set<T>();

    for (auto v : *values) {
      for (auto d : denominations) {
        if (v == d)
          return k;
        else if (v > d)
          newvalues->insert(v - d);
        else
          continue;
      }
    }
    delete values;
    values = newvalues;
  }
  return {};
}


int main() {
    const unsigned nloops = 100000;
    uint64_t sum = 0;
    auto start = std::chrono::high_resolution_clock::now();
    for ( unsigned j=0; j<nloops; ++j ) {
        sum += *minimum_coins<int>(97, std::vector<int>({11, 10, 1}));
        sum += *minimum_coins<int>(13, std::vector<int>({9, 5, 3, 1}));
    }
    auto finish = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> diff = finish - start;
    std::cout << "Duration:" << diff.count() << " Per loop:" << diff.count()/double(nloops) << "\n";
    std::cout << "Sum: " << sum << "\n";
    return 0;
}