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 nbool 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 ndef 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# Implementationusing 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 nstatic 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 nfunction 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' centslet result = can_make_change(target, k, coins, n);// Print the resultif (result) { console.log("1");} else { console.log("0");}// This code is contributed by Tapesh(tapeshdua420) |
Output
1
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.
- For each coin in the array coins, do the following:
- 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 coinsbool 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 Sonigaradef 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 = 5K = 3target = 11coins = [1, 10, 5, 8, 6]# Function callresult = 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 Sonigarafunction 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 callconst result = makeChanges(N, K, target, coins);if (result) { console.log('1');} else { console.log('0');} |
Output
1
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
