A recursive algorithm to find the number of distinct quantities of money from a pile of coins Problem: find the number of distinct quantities of money that a pile of coins can make. 

The vector coins contains the values of the coins, and the corresponding vector quantity contains the number of coin there are (let's say coins = {1} and quantity = {5}, this means I have 5 pennies).  

Although I have solved this problem, I would like to make it more time efficient. Could someone give me some pointers?

Miscellaneous info: the variable ctq stands for "coins to quantity". I solved this by systematically iterating through all possible combinations of coins and putting their sum into a set. There has to be a better way to solve this problem, because this problem is supposed to be a dynamic programming question and I solved this problem without any knowledge of what that's supposed to be.

#include&lt;iostream&gt;
#include&lt;vector&gt;
#include&lt;map&gt;
#include&lt;set&gt;

int money(std::map&lt;int, int&gt; x)
{
    int sum=0;
    for(auto it=x.begin(); it!=x.end(); ++it)
    {
        sum+=it-&gt;first*it-&gt;second;
    }
    return sum;
}

int rec
(
    std::set&lt;int&gt; &amp;sums,
    std::map&lt;int, int&gt; ctq,
    std::vector&lt;int&gt; coins,
    std::vector&lt;int&gt; quantity,
    int m
)
{
    for(int k=quantity[m]; k&gt;=0; k--)
    {
        ctq[coins[m]] = k;
        sums.insert(money(ctq));
        if(m != 0)
        {
            rec(sums, ctq, coins, quantity, m-1);
        }
    }
    return sums.size()-1;
}

int possibleSums(std::vector&lt;int&gt; coins, std::vector&lt;int&gt; quantity)
{
    std::map&lt;int, int&gt; ctq;
    for(std::size_t i=0; i&lt;coins.size(); i++)
    {
        if(ctq.find(coins[i]) == ctq.end())
        {
            ctq.insert(std::make_pair(coins[i], quantity[i]));
        }
        else
        {
            ctq[coins[i]] += quantity[i];
        }
    }

    std::vector&lt;int&gt; n_coins, n_quantity;
    for(auto it = ctq.begin(); it != ctq.end(); ++it)
    {
        n_coins.push_back(it-&gt;first);
        n_quantity.push_back(it-&gt;second);
    }

    std::set&lt;int&gt; sums;
    return rec(sums, ctq, n_coins, n_quantity, n_coins.size()-1);
}

int main()
{
    std::vector&lt;int&gt; coins = {10, 50, 100, 200};
    std::vector&lt;int&gt; quantity = {511, 22, 30, 50};
    std::cout &lt;&lt; possibleSums(coins, quantity) &lt;&lt; "\n";
    return 0;
}
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&lt;int&gt; sums;
for(int c = 0; c &lt; coins.size(); ++c)
{
    // Include zero on the initial list, but not subsequent ones
    if(sums.empty()) 
    {
        for(int q = 0; q &lt;= quantity[c]; ++q) 
        {
            sums.insert(q * coins[c]);
        }
    }
    else
    {
        std::vector&lt;int&gt; current(sums.begin(), sums.end());
        for(int q = 1; q &lt;= quantity[c]; ++q)
        {
            for(int 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.

std::vector&lt;int&gt; sums;
for(int c = 0; c &lt; coins.size(); ++c)
{
    // Include zero on the initial list, but not subsequent ones
    if(sums.empty()) 
    {
        for(int q = 0; q &lt;= quantity[c]; ++q) 
        {
            sums.push_back(q * coins[c]);
        }
    }
    else
    {
        int oldSize = sums.size();
        for(int q = 1; q &lt;= quantity[c]; ++q)
        {
            for(int i = 0; i &lt; oldSize; ++i) 
            {
                sums.push_back(sums[i] + q * coins[c]);
            }
        }
    }
}  

std::sort(sums.begin(), sums.end());
sums.erase(std::unique(sums.begin(), sums.end()), sums.end());