Skip to content

Instantly share code, notes, and snippets.

@abigagli
Last active February 18, 2019 14:17
Show Gist options
  • Save abigagli/8da0faeef7239f95dae279383eea4b51 to your computer and use it in GitHub Desktop.
Save abigagli/8da0faeef7239f95dae279383eea4b51 to your computer and use it in GitHub Desktop.
Brute force solution for number of ways to make a change in C++
#include <vector>
#include <set>
//Just a brute force recursive solution, to be used as a first step in finding the optimal solution, i.e. by adding memoization
//and then possibly flipping into a table-based bottom-up solution
namespace with_multiset
{
void make_change (int amount, std::vector<int> const &coins, std::set<std::multiset<int>> &changes, std::multiset<int> partial = {})
{
if (amount == 0)
{
changes.insert(partial);
return;
}
int res = 0;
for (auto c : coins)
{
if (c <= amount)
{
auto where = partial.insert(c);
make_change(amount - c, coins, changes, partial);
partial.erase(where);
}
}
}
std::set<std::multiset<int>> make_change (int amount, std::vector<int> const &coins)
{
std::set<std::multiset<int>> changes;
make_change(amount, coins, changes);
return changes;
}
}//namespace with_multiset
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment