322 Coin Change

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

Note: You may assume that you have an infinite number of each kind of coin.

//attempt 1: This method does NOT work for all cases.

#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>

using namespace std;

void print1d(vector<int> &nums) { for (auto i : nums) cout << i << ' '; cout << endl; }

int coinChange(vector<int>& coins, int amount) {
    sort(coins.begin(), coins.end());
    int reset = amount;
    int amountOfTimeDivided;

    // swapping positions
    int swap1 = coins.size() - 1;
    int swap2 = swap1 - 1;

    // could be some other combination of coins
    while (true)
    {
        // reset parameters, and try again
        int checkIfChanged = amount = reset;
        int coinCounter = 0;

        for (int i = coins.size() - 1; i >= 0; i--) {
            amountOfTimeDivided = floor(amount / coins.at(i));
            amount = amount % coins.at(i);

            // current coin successfully divided
            if (checkIfChanged != amount) {
                coinCounter += amountOfTimeDivided;
                checkIfChanged = amount;
            }
        }

        // all the change was given from the coin set
        if (amount == 0) {
            return coinCounter;
        }

        // swap for the next largest possible element
        else if (swap2 >= 0) {
            std::iter_swap(coins.begin() + swap1, coins.begin() + swap2);
            swap1--; swap2--;
        }

        else return -1;

        print1d(coins);
    }

}

int main()
{
    vector<int> coins = { 186,419,83,408 };
    int counter = coinChange(coins,6249);
    cout << counter;
}

//attempt2

Last updated