# Generate minimum number of coins that make a given value

Here given code implementation process.

``````import java.util.Arrays;
import java.util.Stack;
/*
Java program for
Generate minimum number of coins that make a given value
*/
public class Combination
{
public boolean minCoinChange(int[] coins,
Stack < Integer > value,
int index, int x, int sum)
{
if (sum == x)
{
return true;
}
if (index < 0 || sum > x)
{
return false;
}
for (int i = index; i >= 0; --i)
{
if ((i == 0 || (i > 0 && coins[i] != coins[i - 1])) && coins[i] > 0)
{
// When i is zero or
// Or No two consecutive coin are similar.
// And coin have a valid value.
value.push(coins[i]);
if (minCoinChange(coins, value, i, x, sum + coins[i]))
{
// When result get
return true;
}
// Remove coin
value.pop();
}
}
return false;
}
public void minimumCoin(int[] coins, int n, int x)
{
if (x < 0 || n <= 0)
{
// Invalid input
return;
}
Stack < Integer > value = new Stack < Integer > ();
System.out.println(" Target : " + x);
// Arrange coin in increasing order
Arrays.sort(coins);
if (minCoinChange(coins, value, n - 1, x, 0))
{
while (value.size() > 0)
{
System.out.print(" " + value.peek());
value.pop();
}
System.out.print("\n");
}
else
{
System.out.println("\nNo Result\n");
}
}
public static void main(String[] args)
{
int[] coins = {
5 , 7 , 4 , 2 , 3
};
int n = coins.length;
// Test A
// x = 27
// Test B
// x = 13
// Test C
// x = 21
// Test D
// x = 36
// Test E
// x = 36
}
}``````

#### Output

`````` Target : 27
2 4 7 7 7
Target : 13
2 4 7
Target : 21
7 7 7
Target : 36
3 5 7 7 7 7
Target : 22
3 5 7 7``````
``````// Include header file
#include <iostream>
#include <stack>
#include <algorithm>

using namespace std;
/*
C++ program for
Generate minimum number of coins that make a given value
*/
class Combination
{
public: bool minCoinChange(
int coins[], stack < int > &value,
int index, int x, int sum)
{
if (sum == x)
{
return true;
}
if (index < 0 || sum > x)
{
return false;
}
for (int i = index; i >= 0; --i)
{
if ((i == 0 || (i > 0 && coins[i] != coins[i - 1])) &&
coins[i] > 0)
{
// When i is zero or
// Or No two consecutive coin are similar.
// And coin have a valid value.
value.push(coins[i]);
if (this->minCoinChange(coins,
value,
i, x,
sum + coins[i]))
{
// When result get
return true;
}
// Remove coin
value.pop();
}
}
return false;
}
void minimumCoin(int coins[], int n, int x)
{
if (x < 0 || n <= 0)
{
// Invalid input
return;
}
stack < int > value;
cout << " Target : " << x << endl;
// Arrange coin in increasing order
sort(coins, coins + n);
if (this->minCoinChange(coins, value, n - 1, x, 0))
{
while (value.size() > 0)
{
cout << " " << value.top();
value.pop();
}
cout << "\n";
}
else
{
cout << "\nNo Result\n" << endl;
}
}
};
int main()
{
int coins[] = {
5 , 7 , 4 , 2 , 3
};
int n = sizeof(coins) / sizeof(coins[0]);
// Test A
// x = 27
// Test B
// x = 13
// Test C
// x = 21
// Test D
// x = 36
// Test E
// x = 36
return 0;
}``````

#### Output

`````` Target : 27
2 4 7 7 7
Target : 13
2 4 7
Target : 21
7 7 7
Target : 36
3 5 7 7 7 7
Target : 22
3 5 7 7``````
``````// Include namespace system
using System;
using System.Collections.Generic;
/*
Csharp program for
Generate minimum number of coins that make a given value
*/
public class Combination
{
public Boolean minCoinChange(
int[] coins,
Stack < int > value,
int index, int x, int sum)
{
if (sum == x)
{
return true;
}
if (index < 0 || sum > x)
{
return false;
}
for (int i = index; i >= 0; --i)
{
if ((i == 0 || (i > 0 && coins[i] != coins[i - 1])) &&
coins[i] > 0)
{
// When i is zero or
// Or No two consecutive coin are similar.
// And coin have a valid value.
value.Push(coins[i]);
if (this.minCoinChange(coins, value, i, x, sum + coins[i]))
{
// When result get
return true;
}
// Remove coin
value.Pop();
}
}
return false;
}
public void minimumCoin(int[] coins, int n, int x)
{
if (x < 0 || n <= 0)
{
// Invalid input
return;
}
Stack < int > value = new Stack < int > ();
Console.WriteLine(" Target : " + x);
// Arrange coin in increasing order
Array.Sort(coins);
if (this.minCoinChange(coins, value, n - 1, x, 0))
{
while (value.Count > 0 )
{
Console.Write(" " + value.Peek());
value.Pop();
}
Console.Write("\n");
}
else
{
Console.WriteLine("\nNo Result\n");
}
}
public static void Main(String[] args)
{
int[] coins = {
5 , 7 , 4 , 2 , 3
};
int n = coins.Length;
// Test A
// x = 27
// Test B
// x = 13
// Test C
// x = 21
// Test D
// x = 36
// Test E
// x = 36
}
}``````

#### Output

`````` Target : 27
2 4 7 7 7
Target : 13
2 4 7
Target : 21
7 7 7
Target : 36
3 5 7 7 7 7
Target : 22
3 5 7 7``````
``````package main
import "sort"
import "fmt"
/*
Go program for
Generate minimum number of coins that make a given value
*/

func minCoinChange(coins[] int,
value *[]int, index int,
x int, sum int) bool {
if sum == x {
return true
}
if index < 0 || sum > x {
return false
}
for i := index ; i >= 0 ; i-- {
if (i == 0 || (i > 0 && coins[i] != coins[i - 1])) && coins[i] > 0 {
// When i is zero or
// Or No two consecutive coin are similar.
// And coin have a valid value.
*value = append(*value, coins[i])
if minCoinChange(coins, value, i, x, sum + coins[i]) {
// When result get
return true
}
// Remove coin
*value = (*value)[: len(*value) - 1]
}
}
return false
}
func minimumCoin(coins[] int, n int, x int) {
if x < 0 || n <= 0 {
// Invalid input
return
}
var value = make([] int, 0)
fmt.Println(" Target : ", x)
// Arrange coin in increasing order
sort.Ints(coins)
if minCoinChange(coins, &value, n - 1, x, 0) {
for (len(value) > 0 ) {
fmt.Print(" ", value[len(value) - 1])
value = value[: len(value) - 1]
}
fmt.Print("\n")
} else {
fmt.Println("\nNo Result\n")
}
}
func main() {

var coins = [] int { 5 , 7 , 4 , 2 , 3 }
var n int = len(coins)
// Test A
// x = 27
minimumCoin(coins, n, 27)
// Test B
// x = 13
minimumCoin(coins, n, 13)
// Test C
// x = 21
minimumCoin(coins, n, 21)
// Test D
// x = 36
minimumCoin(coins, n, 36)
// Test E
// x = 36
minimumCoin(coins, n, 22)
}``````

#### Output

`````` Target : 27
2 4 7 7 7
Target : 13
2 4 7
Target : 21
7 7 7
Target : 36
3 5 7 7 7 7
Target : 22
3 5 7 7``````
``````<?php
/*
Php program for
Generate minimum number of coins that make a given value
*/
class Combination
{
public	function minCoinChange(\$coins, &\$value, \$index, \$x, \$sum)
{
if (\$sum == \$x)
{
return true;
}
if (\$index < 0 || \$sum > \$x)
{
return false;
}
for (\$i = \$index; \$i >= 0; --\$i)
{
if ((\$i == 0 ||
(\$i > 0 && \$coins[\$i] != \$coins[\$i - 1])) &&
\$coins[\$i] > 0)
{
// When i is zero or
// Or No two consecutive coin are similar.
// And coin have a valid value.
array_push(\$value, \$coins[\$i]);
if (\$this->minCoinChange(\$coins, \$value,
\$i, \$x, \$sum + \$coins[\$i]))
{
// When result get
return true;
}
// Remove coin
array_pop(\$value);
}
}
return false;
}
public	function minimumCoin(\$coins, \$n, \$x)
{
if (\$x < 0 || \$n <= 0)
{
// Invalid input
return;
}
\$value = array();
echo(" Target : ".\$x."\n");
// Arrange coin in increasing order
sort(\$coins);
if (\$this->minCoinChange(\$coins, \$value, \$n - 1, \$x, 0))
{
while (empty(\$value) == false)
{
echo(" ".end(\$value));
array_pop(\$value);
}
echo("\n");
}
else
{
echo("\nNo Result\n");
}
}
}

function main()
{
\$coins = array(5, 7, 4, 2, 3);
\$n = count(\$coins);
// Test A
// x = 27
// Test B
// x = 13
// Test C
// x = 21
// Test D
// x = 36
// Test E
// x = 36
}
main();``````

#### Output

`````` Target : 27
2 4 7 7 7
Target : 13
2 4 7
Target : 21
7 7 7
Target : 36
3 5 7 7 7 7
Target : 22
3 5 7 7``````
``````/*
Node JS program for
Generate minimum number of coins that make a given value
*/
class Combination
{
minCoinChange(coins, value, index, x, sum)
{
if (sum == x)
{
return true;
}
if (index < 0 || sum > x)
{
return false;
}
for (var i = index; i >= 0; --i)
{
if ((i == 0 || (i > 0 &&
coins[i] != coins[i - 1]))
&& coins[i] > 0)
{
// When i is zero or
// Or No two consecutive coin are similar.
// And coin have a valid value.
value.push(coins[i]);
if (this.minCoinChange(coins,
value, i, x,
sum + coins[i]))
{
// When result get
return true;
}
// Remove coin
value.pop();
}
}
return false;
}
minimumCoin(coins, n, x)
{
if (x < 0 || n <= 0)
{
// Invalid input
return;
}
var value = [];
console.log(" Target : " + x);
// Arrange coin in increasing order
coins.sort(function(a, b)
{
return a - b;
});
if (this.minCoinChange(coins, value, n - 1, x, 0))
{
while ((value.length == 0) == false)
{
process.stdout.write(" " + value[value.length - 1]);
value.pop();
}
process.stdout.write("\n");
}
else
{
console.log("\nNo Result\n");
}
}
}

function main()
{
var coins = [5, 7, 4, 2, 3];
var n = coins.length;
// Test A
// x = 27
// Test B
// x = 13
// Test C
// x = 21
// Test D
// x = 36
// Test E
// x = 36
}
main();``````

#### Output

`````` Target : 27
2 4 7 7 7
Target : 13
2 4 7
Target : 21
7 7 7
Target : 36
3 5 7 7 7 7
Target : 22
3 5 7 7``````
``````#  Python 3 program for
#  Generate minimum number of coins that make a given value
class Combination :
def minCoinChange(self, coins, value, index, x, sum) :
if (sum == x) :
return True

if (index < 0 or sum > x) :
return False

i = index
while (i >= 0) :
if ((i == 0 or(i > 0 and
coins[i] != coins[i - 1])) and
coins[i] > 0) :
#  When i is zero or
#  Or No two consecutive coin are similar.
#  And coin have a valid value.
value.append(coins[i])
if (self.minCoinChange(coins, value,
i, x,
sum + coins[i])) :
#  When result get
return True

#  Remove coin
value.pop()

i -= 1

return False

def minimumCoin(self, coins, n, x) :
if (x < 0 or n <= 0) :
#  Invalid input
return

value = []
print(" Target : ", x)
#  Arrange coin in increasing order
coins.sort()
if (self.minCoinChange(coins, value, n - 1, x, 0)) :
while ((len(value) == 0) == False) :
print(" ", value[-1], end = "")
value.pop()

print(end = "\n")
else :
print("\nNo Result\n")

def main() :
coins = [5, 7, 4, 2, 3]
n = len(coins)
#  Test A
#  x = 27
#  Test B
#  x = 13
#  Test C
#  x = 21
#  Test D
#  x = 36
#  Test E
#  x = 36

if __name__ == "__main__": main()``````

#### Output

`````` Target :  27
2  4  7  7  7
Target :  13
2  4  7
Target :  21
7  7  7
Target :  36
3  5  7  7  7  7
Target :  22
3  5  7  7``````
``````#  Ruby program for
#  Generate minimum number of coins that make a given value
class Combination
def minCoinChange(coins, value, index, x, sum)
if (sum == x)
return true
end

if (index < 0 || sum > x)
return false
end

i = index
while (i >= 0)
if ((i == 0 || (i > 0 &&
coins[i] != coins[i - 1])) &&
coins[i] > 0)
#  When i is zero or
#  Or No two consecutive coin are similar.
#  And coin have a valid value.
value.push(coins[i])
if (self.minCoinChange(coins, value,
i, x, sum + coins[i]))
#  When result get
return true
end

#  Remove coin
value.pop()
end

i -= 1
end

return false
end

def minimumCoin(coins, n, x)
if (x < 0 || n <= 0)
#  Invalid input
return
end

value = []
print(" Target : ", x, "\n")
#  Arrange coin in increasing order
coins = coins.sort
if (self.minCoinChange(coins, value, n - 1, x, 0))
while ((value.length == 0) == false)
print(" ", value.last)
value.pop()
end

print("\n")
else

print("\nNo Result\n", "\n")
end

end

end

def main()
coins = [5, 7, 4, 2, 3]
n = coins.length
#  Test A
#  x = 27
#  Test B
#  x = 13
#  Test C
#  x = 21
#  Test D
#  x = 36
#  Test E
#  x = 36
end

main()``````

#### Output

`````` Target : 27
2 4 7 7 7
Target : 13
2 4 7
Target : 21
7 7 7
Target : 36
3 5 7 7 7 7
Target : 22
3 5 7 7
``````
``````import scala.collection.mutable._;
/*
Scala program for
Generate minimum number of coins that make a given value
*/
class Combination()
{
def minCoinChange(
coins: Array[Int],
value: Stack[Int],
index: Int,
x: Int,
sum: Int): Boolean = {
if (sum == x)
{
return true;
}
if (index < 0 || sum > x)
{
return false;
}
var i: Int = index;
while (i >= 0)
{
if ((i == 0 || (i > 0 && coins(i) != coins(i - 1))) && coins(i) > 0)
{
// When i is zero or
// Or No two consecutive coin are similar.
// And coin have a valid value.
value.push(coins(i));
if (minCoinChange(coins, value, i, x, sum + coins(i)))
{
// When result get
return true;
}
// Remove coin
value.pop;
}
i -= 1;
}
return false;
}
def minimumCoin(coins: Array[Int], n: Int, x: Int): Unit = {
if (x < 0 || n <= 0)
{
// Invalid input
return;
}
var value: Stack[Int] = new Stack[Int]();
println(" Target : " + x);
// Arrange coin in increasing order

if (minCoinChange(coins.sorted, value, n - 1, x, 0))
{
while (value.isEmpty == false)
{
print(" " + value.top);
value.pop;
}
print("\n");
}
else
{
println("\nNo Result\n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Combination = new Combination();
var coins: Array[Int] = Array(5, 7, 4, 2, 3);
var n: Int = coins.length;
// Test A
// x = 27
// Test B
// x = 13
// Test C
// x = 21
// Test D
// x = 36
// Test E
// x = 36
}
}``````

#### Output

`````` Target : 27
2 4 7 7 7
Target : 13
2 4 7
Target : 21
7 7 7
Target : 36
3 5 7 7 7 7
Target : 22
3 5 7 7``````
``````import Foundation;
/*
Swift 4 program for
Generate minimum number of coins that make a given value
*/
struct Stack
{
private
var items: [Int] = []
func peek()->Int
{
if (self.isEmpty()==false)
{
return items.first!
}
else
{
fatalError("This stack is empty.")
}
}
func isEmpty()->Bool
{
return items.count == 0
}
mutating func pop()
{
items.removeFirst()
}
mutating func push(_ data: Int)
{
items.insert(data, at: 0)
}
}
class Combination
{
func minCoinChange(_ coins: [Int],
_ value: inout Stack,
_ index: Int,
_ x: Int,
_ sum: Int) -> Bool
{
if (sum == x)
{
return true;
}
if (index < 0 || sum > x)
{
return false;
}
var i: Int = index;
while (i >= 0)
{
if ((i == 0 || (i > 0 &&
coins[i]  != coins[i - 1])) &&
coins[i] > 0)
{
// When i is zero or
// Or No two consecutive coin are similar.
// And coin have a valid value.
value.push(coins[i]);
if (self.minCoinChange(coins, &value, i, x, sum + coins[i]))
{
// When result get
return true;
}
// Remove coin
value.pop();
}
i -= 1;
}
return false;
}
func minimumCoin(_ coins: [Int], _ n: Int, _ x: Int)
{
if (x < 0 || n <= 0)
{
// Invalid input
return;
}
var value = Stack();
print(" Target : ", x);

if (self.minCoinChange(coins.sorted(), &value, n - 1, x, 0))
{
while (value.isEmpty() == false)
{
print(" ", value.peek(), terminator: "");
value.pop();
}
print(terminator: "\n");
}
else
{
print("\nNo Result\n");
}
}
}
func main()
{
let coins: [Int] = [5, 7, 4, 2, 3];
let n: Int = coins.count;
// Test A
// x = 27
// Test B
// x = 13
// Test C
// x = 21
// Test D
// x = 36
// Test E
// x = 36
}
main();``````

#### Output

`````` Target :  27
2  4  7  7  7
Target :  13
2  4  7
Target :  21
7  7  7
Target :  36
3  5  7  7  7  7
Target :  22
3  5  7  7``````
``````import java.util.Stack;
/*
Kotlin program for
Generate minimum number of coins that make a given value
*/
class Combination
{
fun minCoinChange(
coins: Array < Int > ,
value: Stack < Int >  ,
index : Int, x: Int,
sum: Int): Boolean
{
if (sum == x)
{
return true;
}
if (index < 0 || sum > x)
{
return false;
}
var i: Int = index;
while (i >= 0)
{
if ((i == 0 ||
(i > 0 && coins[i] != coins[i - 1])) &&
coins[i] > 0)
{
// When i is zero or
// Or No two consecutive coin are similar.
// And coin have a valid value.
value.push(coins[i]);
if (this.minCoinChange(coins,
value, i, x,
sum + coins[i]))
{
// When result get
return true;
}
// Remove coin
value.pop();
}
i -= 1;
}
return false;
}
fun minimumCoin(coins: Array < Int > , n: Int, x: Int): Unit
{
if (x < 0 || n <= 0)
{
// Invalid input
return;
}
val value: Stack < Int > = Stack < Int > ();
println(" Target : " + x);
// Arrange coin in increasing order
coins.sort();
if (this.minCoinChange(coins, value, n - 1, x, 0))
{
while (value.empty() == false)
{
print(" " + value.peek());
value.pop();
}
print("\n");
}
else
{
println("\nNo Result\n");
}
}
}
fun main(args: Array < String > ): Unit
{
val coins: Array < Int > = arrayOf(5, 7, 4, 2, 3);
val n: Int = coins.count();
// Test A
// x = 27
// Test B
// x = 13
// Test C
// x = 21
// Test D
// x = 36
// Test E
// x = 36
}``````

#### Output

`````` Target : 27
2 4 7 7 7
Target : 13
2 4 7
Target : 21
7 7 7
Target : 36
3 5 7 7 7 7
Target : 22
3 5 7 7``````

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.