हिन्दी flagहिन्दी  
CLOSE

Suggested:

Problem Statement

Given an integer array of coins representing coins of different denominations and an integer target representing a total amount of money. Return the fewest number of coins that are needed to make up that target. If that amount of money cannot be made up by any combination of the coins, return -1. There are infinite numbers of coins of each type.

Examples

Example 1:

Input: Target = 11, Coins = [1, 2, 5]
Output: 3

Explanation:
Minimum Number of Coins: 3 (2 coins of 5, and 1 coin of 1)
Example 2:

Input: coins = [2, 5], Target = 3
Output: -1

Explanation: It's not possible to make target 3 with coins of 2 and 5.
Since we can't combine the coin 2 and 5 to make the target 3.
So the output is -1.

Different Approaches

1️⃣ Recursive Approach

Why a Greedy Solution will not work:

As the question asks for minimum number of coins, the first approach that comes to our mind is greedy. A greedy solution will fail in this problem because there is no ‘uniformity’ in data. While selecting a local better choice we may choose an item that will in the long term give less value.

A Greedy solution will be to take the highest denomination coin first, so we will take an item on index 0, with a value of 9. Now the remaining target sum will be 2. Therefore we can only consider coins with a value of 1. We will take 2 coins of value 1 to meet the target. So a greedy solution gives us the answer 3 (9,1,1).

Now we can clearly see that a non-greedy solution of taking 2 coins (6,5) gives a better option. So we can say that the greedy solution doesn’t work for this problem.

As the greedy approach doesn’t work, try to generate all possible combinations using recursion and select the combination which gives the minimum number of coins.

Steps to form the recursive solution:

  • Express the problem in terms of indexes:We are given ‘n’ distinct numbers, where n is the length of the array. Their denomination is represented by the ‘coins’ array. So clearly one parameter will be ‘ind’, i.e index up to which the array items are being considered. There is one more parameter “T”, to know the given target that we want to achieve.
    • So, initially, we need to find f(n-1, T) where T is the initial target given. f(n-1, T) will give the minimum number of coins required to form the target sum by considering coins from index 0 to n-1.
  • Try out all possible choices at a given index: As all the subsets needs to be generated, use the pick/non-pick technique. There will be a slight change for this question which is discussed below.
    We have two choices:
    • Exclude the current element in the subset: First try to find a subset without considering the current index coin. If the current coin is excluded, the target sum will not be affected and the number of coins added to the solution will be 0. So call the recursive function f(ind-1, T).
    • Include the current element in the subset: Try to find a subset by considering the current icoin. As the current coin is included, the target sum will be updated to T-arr[ind], as we have considered 1 coin to be part of the solution.
      • Now here is the catch, as there is an unlimited supply of coins, we want to again form a solution with the same coin value. So we will not recursively call for f(ind-1, T-arr[ind]) rather we will stay at that index only and call for f(ind, T-arr[ind]) to find the answer.

Note: Consider the current coin only when its denomination value (arr[ind]) is less than or equal to the target T.

f(ind, T){
    notTake = 0 + f(ind-1, T)
    take = 1e9
    if(arr[ind] <= T)
         take = 1 + f(ind, T-arr[ind])
}
  • Return the minimum of two choices: As we have to return the minimum number of coins, we will return the minimum of take and notTake as our answer.
f(ind, T){
    notTake = 0 + f(ind-1, T)
    take = 1e9
    if(arr[ind] <= T)
         take = 1 + f(ind, T-arr[ind])
    return min(take, notTake)
}
  • Base Case: If ind==0, it means we are at the first item, so in that case, the following cases can arise:
    • In cases where the target is divisible by the coin element, return (T / arr[0]), as this will give the number of coins needed to make target.
    • In all other cases, where the target is not divisible by the coin, a solution can not be formed, so return a big number like 1e9. This will prevent the coin from getting added to the final solution as we need to return the minimum number of coins.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    /**
     * Helper function to calculate the minimum number of coins
     * needed to form the target amount using recursion.
     * @param coins Vector of coin denominations.
     * @param index Current index in the coin array.
     * @param target Remaining amount to be formed.
     * @return Minimum number of coins required to form the target.
     */
    int findMinCoins(vector<int>& coins, int index, int target) {
        // Base case: If we're at the first coin
        if (index == 0) {
            // If target is divisible by the coin value, return the quotient
            return (target % coins[0] == 0) ? target / coins[0] : 1e9;
        }

        // Do not take the current coin
        int notTaken = findMinCoins(coins, index - 1, target);

        // Take the current coin if it does not exceed the target
        int taken = 1e9; // Initialize to a large value
        if (coins[index] <= target) {
            taken = 1 + findMinCoins(coins, index, target - coins[index]);
        }

        // Return the minimum of taking or not taking the coin
        return min(notTaken, taken);
    }

public:
    /**
     * Function to calculate the minimum number of coins needed to form the target amount.
     * @param coins Vector of coin denominations.
     * @param amount Target amount to be formed.
     * @return Minimum number of coins required, or -1 if not possible.
     */
    int minimumCoins(vector<int>& coins, int amount) {
        int n = coins.size();

        // Use the helper function to compute the result
        int result = findMinCoins(coins, n - 1, amount);

        // If the result is still a large value, it's not possible to form the amount
        return (result >= 1e9) ? -1 : result;
    }
};

int main() {
    vector<int> coins = {1, 2, 3}; // Coin denominations
    int amount = 7; // Target amount

    // Create an instance of the Solution class
    Solution solution;

    // Calculate and print the result
    int result = solution.minimumCoins(coins, amount);
    if (result != -1) {
        cout << "The minimum number of coins needed is " << result << endl;
    } else {
        cout << "It is not possible to form the target amount with the given coins." << endl;
    }

    return 0;
}

Complexity Analysis:

  • Time Complexity: O(2^n), as each element has 2 choices, and there are n elements in the array.
  • Space Complexity: O(n)
    • The stack space will be O(n), the maximum depth of the stack.

 

Intuition:

  1. Start with the target amount:
    1. You start with your target amount and explore all possible combinations of coins to find the minimum number of coins needed to make that amount.
  2. For each coin denomination:
    1. You have two choices:
      1. Include the current coin denomination:
        1. You include the current coin denomination and recursively find the minimum number of coins needed for the remaining target amount.
      2. Exclude the current coin denomination:
        1. You exclude the current coin denomination and move on to the next denomination.
  3. Explore all possible combinations:
    1. You recursively explore all possible combinations by including or excluding each coin denomination until the target amount becomes 0.
  4. Return the minimum number of coins needed:
    1. Once the target amount becomes 0, you return the minimum number of coins needed to make that amount.
min-number-of-coin-make-up-target-recursion.jpg

Visualization:

minCoins(11)
  |            \
minCoins(10)   minCoins(9)
  |          /         \
minCoins(9)  minCoins(8)  minCoins(6)
  |       /   |       /      \
minCoins(8)  minCoins(7)  minCoins(4)
...        ...        ...        ...

2️⃣ Top-Down Approach (Memoization)

If we draw the recursion tree, we will see that there are overlapping subproblems. Hence the DP approaches can be applied to the recursive solution.

image-312.png

In order to convert a recursive solution to memoization the following steps will be taken:

  • Declare a dp array of size [n][target+1]: As there are two changing parameters in the recursive solution, 'ind' and 'target'. The maximum value 'ind' can attain is (n), where n is the size of array and for 'target' only values between 0 to target. Therefore, we need 2D dp array.
    • The dp array stores the calculations of subproblems. Initialize dp array with -1, to indicate that no subproblem has been solved yet.
  • While encountering an overlapping subproblem: When we come across a subproblem, for which the dp array has value other than -1, it means we have found a subproblem which has been solved before hence it is an overlapping subproblem. No need to calculate it's value again just retrieve the value from dp array and return it.
  • Store the value of subproblem: Whenever, a subproblem is encountered and it is not solved yet(the value at this index will be -1 in the dp array), store the calculated value of subproblem in the array.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    /**
     * Helper function to calculate the minimum number of coins
     * needed to form the target amount using memoization.
     * @param coins Vector of coin denominations.
     * @param index Current index in the coin array.
     * @param target Remaining amount to be formed.
     * @param dp Memoization table to store intermediate results.
     * @return Minimum number of coins required to form the target.
     */
    int findMinCoins(vector<int>& coins, int index, int target, vector<vector<int>>& dp) {
        // Base case: If we're at the first coin
        if (index == 0) {
            // If target is divisible by the coin value, return the quotient
            return (target % coins[0] == 0) ? target / coins[0] : 1e9;
        }

        // If already computed, return the stored value
        if (dp[index][target] != -1) {
            return dp[index][target];
        }

        // Do not take the current coin
        int notTaken = findMinCoins(coins, index - 1, target, dp);

        // Take the current coin if it does not exceed the target
        int taken = 1e9; // Initialize to a large value
        if (coins[index] <= target) {
            taken = 1 + findMinCoins(coins, index, target - coins[index], dp);
        }

        // Store the result in the dp table and return it
        return dp[index][target] = min(notTaken, taken);
    }

public:
    /**
     * Function to calculate the minimum number of coins needed to form the target amount.
     * @param coins Vector of coin denominations.
     * @param amount Target amount to be formed.
     * @return Minimum number of coins required, or -1 if not possible.
     */
    int minimumCoins(vector<int>& coins, int amount) {
        int n = coins.size();

        // Create a memoization table initialized to -1
        vector<vector<int>> dp(n, vector<int>(amount + 1, -1));

        // Use the helper function to compute the result
        int result = findMinCoins(coins, n - 1, amount, dp);

        // If the result is still a large value, it's not possible to form the amount
        return (result >= 1e9) ? -1 : result;
    }
};

int main() {
    vector<int> coins = {1, 2, 3}; // Coin denominations
    int amount = 7; // Target amount

    // Create an instance of the Solution class
    Solution solution;

    // Calculate and print the result
    int result = solution.minimumCoins(coins, amount);
    if (result != -1) {
        cout << "The minimum number of coins needed is " << result << endl;
    } else {
        cout << "It is not possible to form the target amount with the given coins." << endl;
    }

    return 0;
}

Complexity Analysis:

  • Time Complexity: O(N*Target), as there are N*Target states therefore at max ‘N*Target’ new problems will be solved.
  • Space Complexity: O(N*Target) + O(N), the stack space will be O(N) and a 2D array of size N*T is used.

Your experience on this site will be improved by allowing cookies Cookie Policy