Instead of calculating each combination recursively, you can build up the list one coinage type at a time. This would involve fewer iterations in the case that any combinations form the same total, and more importantly wouldn't require adding up each combination separately. For example:
std::set<int> sums;
for(int c = 0; c < coins.size(); ++c)
{
// InitialInclude setzero includeson zerothe initial list, othersbut don'tnot subsequent ones
std::set<int> sums; if(sums.empty())
{
for(int q = 0; q < quantity[0];quantity[c]; ++q)
{
sums.insert(q * coins[0]coins[c]);
}
for(int c = 1; c}
< coins.size(); ++c) else
{
std::vector<int> current(sums.begin(), sums.end());
for(int q = 1; q < quantity[c]; ++q)
{
for(auto sum : current)
{
sums.insert(sum + q * coins[c]);
}
}
}
}
Using a vector instead of a set to accumulate sums (removing duplicates at the end) might be faster, and would eliminate the need for a temporary copy (current). However, it wouldn't eliminate the redundant loops based off the same total, so some measurements would be needed to see which is better.