# 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.

```cpp
#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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/322_coin_change.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.