Edit: I should mention that I did come up with this algorithm that uses dynamic programming but I think it only works for certain sets of denominations hence why I said that I failed to come up with an algorithm.
int main()
{
std::unordered_map<int, std::vector<std::pair<std::vector<int>, int>>> m;
m[1].push_back({ { 1 }, 1 });
const int target = 25;
const std::vector<int> coins = { 200, 100, 50, 20, 10, 5, 2, 1 };
for (int i = 2; i <= target; i++) // N
{
std::unordered_set<int> s;
for (auto coin : coins) // M
{
if (coin > i) continue;
if (coin == 1)
{
m[i].push_back({ { i }, 1 });
s.insert(1); // constant
}
for (auto v : m[i - coin]) // N
{
if (s.find(v.second + 1) != s.end()) continue; // constant
std::vector<int> temp_v = v.first;
temp_v.push_back(coin); // constant
m[i].push_back({ temp_v, v.second + 1 }); // constant
s.insert(v.second + 1); // constant
std::cout << i << ": ";
PRINT_ELEMENTS(temp_v);
}
}
}
return 0;
}
The trick I'm using is that for a given target, each combination has a unique number of elements. E.g. for target 5 the combinations are {5}, {2, 2, 1}, {2, 1, 1, 1}, and {1, 1, 1, 1, 1} and as you can see the cardinality of each set is unique. This won't work if, let's say, the denominations were {1, 2, 3, 5, 6} and the target was 8. In that case I can store use arrays/vectors to represent combinations and store them in a set but I'd have to sort each vector first (so that they can be easily compared) and that increases the complexity of my solution quite a bit I think.