Recursive Solution

The recursive solution to the coin change problem involves trying out all possible combinations that add up to the given amount and picking the solution with the minimum number of coins. Let's take a look at the implementation:

1#include <iostream>
2#include <vector>
3#include <climits>
4
5int coinChangeRecursive(std::vector<int>& coins, int amount) {
6    if (amount == 0) {
7        return 0;
8    }
9
10    int minCoins = INT_MAX;
11
12    for (int coin : coins) {
13        if (amount - coin >= 0) {
14            int res = coinChangeRecursive(coins, amount - coin);
15            if (res != INT_MAX) {
16                minCoins = std::min(minCoins, res + 1);
17            }
18        }
19    }
20
21    return minCoins;
22}
23
24int main() {
25    std::vector<int> coins = {1, 2, 5};
26    int amount = 11;
27
28    int minCoins = coinChangeRecursive(coins, amount);
29
30    std::cout << "Minimum number of coins needed: " << minCoins << std::endl;
31
32    return 0;
33}

In this implementation, we define a function coinChangeRecursive that takes in a vector of coin denominations and the target amount of change. If the amount is 0, we return 0 as we don't need any coins to make 0 change.

Otherwise, we iterate over each coin denomination in the given vector. If the difference between the current amount and the coin denomination is greater than or equal to 0, we recursively call coinChangeRecursive with the updated amount (amount - coin). We store the result in the variable res.

If the result is not equal to INT_MAX, indicating a valid combination, we update the minCoins variable by taking the minimum of the current minCoins and res + 1, where res + 1 represents the number of coins used so far.

Finally, we return the minCoins as the minimum number of coins needed to make the given amount of change.

Let's run the code and see the output:

1Minimum number of coins needed: 3

xxxxxxxxxx

}

#include <iostream>

#include <vector>

#include <climits>

​

int coinChangeRecursive(std::vector<int>& coins, int amount) {

    if (amount == 0) {

        return 0;

    }

​

    int minCoins = INT_MAX;

​

    for (int coin : coins) {

        if (amount - coin >= 0) {

            int res = coinChangeRecursive(coins, amount - coin);

            if (res != INT_MAX) {

                minCoins = std::min(minCoins, res + 1);

            }

        }

    }

​

    return minCoins;

}

​

int main() {

    std::vector<int> coins = {1, 2, 5};

    int amount = 11;

​

    int minCoins = coinChangeRecursive(coins, amount);

​