Greedy Algorithm for coin change c++

Question

So, I'm creating a coin change algorithm that take a Value N and any number of denomination and if it doesn't have a 1, i have to include 1 automatically. I already did this, but there is a flaw now i have 2 matrix and i need to use 1 of them. Is it possible to rewrite S[i] matrix and still increase the size of array.... Also how can i find the max denomination and the second highest and sooo on till the smallest? Should i just sort it out in an highest to lowest to make it easier or is there a simpler way to look for them one after another?

int main()
{
    int N,coin;
    bool hasOne;
    cout << "Enter the value N to produce: " << endl;
    cin >> N;
    cout << "Enter number of different coins: " << endl;
    cin >> coin;

    int *S = new int[coin];

    cout << "Enter the denominations to use with a space after it" << endl;
    cout << "(1 will be added if necessary): " << endl;
    for(int i = 0; i < coin; i++)
    {
        cin >> S[i];
        if(S[i] == 1)
        {
            hasOne = true;
        }
        cout << S[i] << " ";
    }
    cout << endl;
    if(!hasOne)
    {
        int *newS = new int[coin];
        for(int i = 0; i < coin; i++)
        {
            newS[i] = S[i];
            newS[coin-1] = 1;
            cout << newS[i] << "  ";
        }
        cout << endl;
        cout << "1 has been included" << endl;
    }

    //system("PAUSE");
    return 0;
}

Answer 1

You could implement it with std::vector, then you only need to use push_back.

std::sort can be used to sort the denominations into descending order, then it's just a matter of checking whether the last is 1 and adding it if it was missing. (There is a lot of error checking missing in this code, for instance, you should probably check that no denomination is >= 0, since you are using signed integers).

#include <iostream>   // for std::cout/std::cin
#include <vector>     // for std::vector
#include <algorithm>  // for std::sort

int main()
{
    std::cout << "Enter the value N to produce:\n";
    int N;
    std::cin >> N;

    std::cout << "Enter the number of different denominations:\n";
    size_t denomCount;
    std::cin >> denomCount;

    std::vector<int> denominations(denomCount);
    for (size_t i = 0; i < denomCount; ++i) {
        std::cout << "Enter denomination #" << (i + 1) << ":\n";
        std::cin >> denominations[i];
    }

    // sort into descending order.
    std::sort(denominations.begin(), denominations.end(),
        [](int lhs, int rhs) { return lhs > rhs; });

    // if the lowest denom isn't 1... add 1.
    if (denominations.back() != 1)
        denominations.push_back(1);

    for (int coin: denominations) {
        int numCoins = N / coin;
        N %= coin;
        if (numCoins > 0)
            std::cout << numCoins << " x " << coin << '\n';
    }

    return 0;
}

Live demo: http://ideone.com/h2SIHs