# 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 = , 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