Coin change problem with limited coins

0 0 10 minutes read

Given three integers n, k, target, and an array of coins[] of size n. Find if it is possible to make a change of target cents by using an infinite supply of each coin but the total number of coins used must be exactly equal to k.

Examples:

Input: n = 5, k = 3, target = 11, coins = {1, 10, 5, 8, 6}
Output: 1
Explanation: 2 coins of 5 and 1 coin of 1 can be used to make a change of 11 i.e. 11 => 5 + 5 + 1.

Input: n = 3, k = 5, target = 25, coins = {7, 2, 4}
Output: 1
Explanation: 3 coins 7, 2 coins of 2 can be used to make a change of 25 i.e. 25 => 7+7+7+2+2.

Naive Approach :

The basic way to solve this problem is to generate all possible combinations by using a recursive approach.

Below are the steps involved in the implementation of the code:

If target == 0 and k == 0, return true
If n == 0 or target < 0 or k < 0, return false
Otherwise, the result is true if either of the following conditions is satisfied:
- Include the last coin and recursively check if it is possible to make the remaining target using k-1 coins.
- Exclude the last coin and recursively check if it is possible to make the target using the remaining n-1 coins and k coins.

below is the code implementation of the above code:

C++

#include <bits/stdc++.h>
using namespace std;
 
// Function to check if it is possible to make a change of
// target cents using exactly k coins from the given coins
// array of size n
bool canMakeChange(int target, int k, int coins[], int n)
{
    // If target and k are both 0, then we have found a
    // valid combination of coins
    if (target == 0 && k == 0) {
        return true;
    }
    // If n becomes 0 or target or k becomes negative, then
    // the current combination of coins is not valid
    if (n == 0 || target < 0 || k < 0) {
        return false;
    }
    // we can either include the current coin or exclude it
    // We check if it is possible to make the change by
    // including the current coin or excluding it
    return canMakeChange(target - coins[n - 1], k - 1,
                         coins, n)
           || canMakeChange(target, k, coins, n - 1);
}
 
int main()
{
    int n = 5;
    int k = 3;
    int target = 11;
    int coins[] = { 1, 10, 5, 8, 6 };
 
    // Check if it is possible to make the change using 'k'
    // coins from the 'coins' array to get 'target' cents
    bool result = canMakeChange(target, k, coins, n);
 
    // Print the result
    if (result) {
        cout << "1" << endl;
    }
    else {
        cout << "0" << endl;
    }
    return 0;
}

Java

import java.util.Arrays;
 
class GFG {
     
    // Function to check if it is possible to make a change of
    // target cents using exactly k coins from the given coins
    // array of size n
    static boolean canMakeChange(int target, int k, int[] coins, int n) {
        // If target and k are both 0, then we have found a
        // valid combination of coins
        if (target == 0 && k == 0) {
            return true;
        }
        // If n becomes 0 or target or k becomes negative, then
        // the current combination of coins is not valid
        if (n == 0 || target < 0 || k < 0) {
            return false;
        }
        // we can either include the current coin or exclude it
        // We check if it is possible to make the change by
        // including the current coin or excluding it
        return canMakeChange(target - coins[n - 1], k - 1, coins, n)
                || canMakeChange(target, k, coins, n - 1);
    }
     
    public static void main(String[] args) {
        int n = 5;
        int k = 3;
        int target = 11;
        int[] coins = { 1, 10, 5, 8, 6 };
 
        // Check if it is possible to make the change using 'k'
        // coins from the 'coins' array to get 'target' cents
        boolean result = canMakeChange(target, k, coins, n);
 
        // Print the result
        if (result) {
            System.out.println("1");
        } else {
            System.out.println("0");
        }
    }
}
 
// This code is contributed by shivamgupta0987654321

Python3

# python Implementation
 
# Function to check if it is possible to make a change of
# target cents using exactly k coins from the given coins
# array of size n
def can_make_change(target, k, coins, n):
    # If target and k are both 0, then we have found a
    # valid combination of coins
    if target == 0 and k == 0:
        return True
    # If n becomes 0 or target or k becomes negative, then
    # the current combination of coins is not valid
    if n == 0 or target < 0 or k < 0:
        return False
    # we can either include the current coin or exclude it
    # We check if it is possible to make the change by
    # including the current coin or excluding it
    return can_make_change(target - coins[n - 1], k - 1, coins, n) or can_make_change(target, k, coins, n - 1)
 
def main():
    n = 5
    k = 3
    target = 11
    coins = [1, 10, 5, 8, 6]
 
    # Check if it is possible to make the change using 'k'
    # coins from the 'coins' array to get 'target' cents
    result = can_make_change(target, k, coins, n)
 
    # Print the result
    if result:
        print("1")
    else:
        print("0")
 
if __name__ == "__main__":
    main()

C#

// C# Implementation
using System;
 
class GFG {
     
// Function to check if it is possible to make a change of
// target cents using exactly k coins from the given coins
// array of size n
static bool canMakeChange(int target, int k, int[] coins, int n)
{
    // If target and k are both 0, then we have found a
    // valid combination of coins
    if (target == 0 && k == 0) {
        return true;
    }
    // If n becomes 0 or target or k becomes negative, then
    // the current combination of coins is not valid
    if (n == 0 || target < 0 || k < 0) {
        return false;
    }
    // we can either include the current coin or exclude it
    // We check if it is possible to make the change by
    // including the current coin or excluding it
    return canMakeChange(target - coins[n - 1], k - 1,
                        coins, n)
        || canMakeChange(target, k, coins, n - 1);
}
 
public static int Main()
{
    int n = 5;
    int k = 3;
    int target = 11;
    int[] coins = { 1, 10, 5, 8, 6 };
 
    // Check if it is possible to make the change using 'k'
    // coins from the 'coins' array to get 'target' cents
    bool result = canMakeChange(target, k, coins, n);
 
    // Print the result
    if (result) {
        Console.WriteLine("1");
    }
    else {
        Console.WriteLine("0");
    }
    return 0;
}
 
}
 
// This code is contributed by Utkarsh Kumar

Javascript

// JavaScript Implementation
 
// Function to check if it is possible to make a change of
// target cents using exactly k coins from the given coins
// array of size n
function can_make_change(target, k, coins, n) {
    // If target and k are both 0, then we have found a
    // valid combination of coins
    if (target === 0 && k === 0) {
        return true;
    }
    // If n becomes 0 or target or k becomes negative, then
    // the current combination of coins is not valid
    if (n === 0 || target < 0 || k < 0) {
        return false;
    }
    // we can either include the current coin or exclude it
    // We check if it is possible to make the change by
    // including the current coin or excluding it
    return can_make_change(target - coins[n - 1], k - 1, coins, n) || can_make_change(target, k, coins, n - 1);
}
 
let n = 5;
let k = 3;
let target = 11;
let coins = [1, 10, 5, 8, 6];
 
// Check if it is possible to make the change using 'k'
// coins from the 'coins' array to get 'target' cents
let result = can_make_change(target, k, coins, n);
 
// Print the result
if (result) {
    console.log("1");
} else {
    console.log("0");
}
 
// This code is contributed by Tapesh(tapeshdua420)

Output

Time Complexity : O(2^(k+n))
Space Complexity : O(k+n)

Efficient Approach: This can be solved with the following idea:

The approach used is a dynamic programming approach, The approach works by building a table of subproblems using a two-dimensional boolean array. The approach iterates over all values of i from 1 to target and all values of j from 0 to K. For each subproblem dp[i][j], the algorithm checks whether any of the coins in the array can be used to add up to i while using j-1 coins to add up to the remaining value. If so, the subproblem is marked as solved by setting dp[i][j] = true. The algorithm returns dp[target][K] as the solution to the original problem.

Below are the steps involved in the implementation of the code:

Initialize a two-dimensional boolean array dp of size (target+1) x (K+1).
Set the base case dp[0][0] = true.
For i from 1 to target and j from 0 to K, do the following:
- For each coin in the array coins, do the following:
  - If the current coin denomination is less than or equal to i, and j > 0 (i.e., there are still coins remaining to be used), and dp[i-coin][j-1] is true, then set dp[i][j] to true and break out of the loop over coins.
Return dp[target][K] as the solution to the original problem.

below is the code implementation of the above code:

C++

// Nikunj Sonigara
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check whether target can be achieved by K coins
bool makeChanges(int N, int K, int target, vector<int>& coins) {
    vector<vector<bool>> dp(target + 1, vector<bool>(K + 1, false));
    dp[0][0] = true;
 
    for (int i = 1; i <= target; i++) {
        for (int j = 0; j <= K; j++) {
            for (int coin : coins) {
                if (coin <= i && j > 0 && dp[i - coin][j - 1]) {
                    dp[i][j] = true;
                    break;
                }
            }
        }
    }
 
    // Return the result
    return dp[target][K];
}
 
int main() {
    int N = 5;
    int K = 3;
    int target = 11;
    vector<int> coins = {1, 10, 5, 8, 6};
 
    // Function call
    bool result = makeChanges(N, K, target, coins);
    if (result) {
        cout << '1' << endl;
    } else {
        cout << '0' << endl;
    }
 
    return 0;
}

Java

// java code for the above approach:
import java.util.*;
 
public class CoinChangeProblem {
 
    // Function to check whether target
    // can be achieved by K coins
    public static boolean
    makeChanges(int N, int K, int target, int[] coins)
    {
        boolean[][] dp = new boolean[target + 1][K + 1];
        dp[0][0] = true;
 
        for (int i = 1; i <= target; i++) {
            for (int j = 0; j <= K; j++) {
                for (int coin : coins) {
                    if (coin <= i && j > 0
                        && dp[i - coin][j - 1]) {
                        dp[i][j] = true;
                        break;
                    }
                }
            }
        }
 
        // Return the result
        return dp[target][K];
    }
 
    // Driver codes
    public static void main(String[] args)
    {
        int N = 5;
        int K = 3;
        int target = 11;
        int[] coins = { 1, 10, 5, 8, 6 };
 
        // Function call
        boolean result = makeChanges(N, K, target, coins);
        if (result == true) {
            System.out.println('1');
        }
        else {
            System.out.println('0');
        }
    }
}

Python

# Nikunj Sonigara
 
def make_changes(N, K, target, coins):
    dp = [[False for _ in range(K + 1)] for _ in range(target + 1)]
    dp[0][0] = True
 
    for i in range(1, target + 1):
        for j in range(K + 1):
            for coin in coins:
                if coin <= i and j > 0 and dp[i - coin][j - 1]:
                    dp[i][j] = True
                    break
 
    # Return the result
    return dp[target][K]
 
N = 5
K = 3
target = 11
coins = [1, 10, 5, 8, 6]
 
# Function call
result = make_changes(N, K, target, coins)
if result:
    print('1')
else:
    print('0')

C#

using System;
 
public class CoinChangeProblem
{
    // Function to check whether target
    // can be achieved by K coins
    public static bool MakeChanges(int N, int K, int target, int[] coins)
    {
        bool[,] dp = new bool[target + 1, K + 1];
        dp[0, 0] = true;
        for (int i = 1; i <= target; i++)
        {
            for (int j = 0; j <= K; j++)
            {
                foreach (int coin in coins)
                {
                    if (coin <= i && j > 0 && dp[i - coin, j - 1])
                    {
                        dp[i, j] = true;
                        break;
                    }
                }
            }
        }
        // Return the result
        return dp[target, K];
    }
    // Driver codes
    public static void Main(string[] args)
    {
        int N = 5;
        int K = 3;
        int target = 11;
        int[] coins = { 1, 10, 5, 8, 6 };
        // Function call
        bool result = MakeChanges(N, K, target, coins);
        if (result == true)
        {
            Console.WriteLine('1');
        }
        else
        {
            Console.WriteLine('0');
        }
    }
}

Javascript

// Nikunj Sonigara
 
function makeChanges(N, K, target, coins) {
    const dp = new Array(target + 1);
    for (let i = 0; i <= target; i++) {
        dp[i] = new Array(K + 1).fill(false);
    }
    dp[0][0] = true;
 
    for (let i = 1; i <= target; i++) {
        for (let j = 0; j <= K; j++) {
            for (const coin of coins) {
                if (coin <= i && j > 0 && dp[i - coin][j - 1]) {
                    dp[i][j] = true;
                    break;
                }
            }
        }
    }
 
    // Return the result
    return dp[target][K];
}
 
const N = 5;
const K = 3;
const target = 11;
const coins = [1, 10, 5, 8, 6];
 
// Function call
const result = makeChanges(N, K, target, coins);
if (result) {
    console.log('1');
} else {
    console.log('0');
}

Output

Time Complexity: O(NKT)
Auxiliary Space: O(NKT)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!