Posted on by Kalkicode
Code Backtracking

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.
				// Add coin
				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)
	{
		Combination task = new Combination();
		int[] coins = {
			5 , 7 , 4 , 2 , 3
		};
		int n = coins.length;
		// Test A
		// x = 27
		task.minimumCoin(coins, n, 27);
		// Test B
		// x = 13
		task.minimumCoin(coins, n, 13);
		// Test C
		// x = 21
		task.minimumCoin(coins, n, 21);
		// Test D
		// x = 36
		task.minimumCoin(coins, n, 36);
		// Test E
		// x = 36
		task.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
// 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.
				// Add coin
				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()
{
	Combination *task = new Combination();
	int coins[] = {
		5 , 7 , 4 , 2 , 3
	};
	int n = sizeof(coins) / sizeof(coins[0]);
	// Test A
	// x = 27
	task->minimumCoin(coins, n, 27);
	// Test B
	// x = 13
	task->minimumCoin(coins, n, 13);
	// Test C
	// x = 21
	task->minimumCoin(coins, n, 21);
	// Test D
	// x = 36
	task->minimumCoin(coins, n, 36);
	// Test E
	// x = 36
	task->minimumCoin(coins, n, 22);
	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.
				// Add coin
				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)
	{
		Combination task = new Combination();
		int[] coins = {
			5 , 7 , 4 , 2 , 3
		};
		int n = coins.Length;
		// Test A
		// x = 27
		task.minimumCoin(coins, n, 27);
		// Test B
		// x = 13
		task.minimumCoin(coins, n, 13);
		// Test C
		// x = 21
		task.minimumCoin(coins, n, 21);
		// Test D
		// x = 36
		task.minimumCoin(coins, n, 36);
		// Test E
		// x = 36
		task.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
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.
			// Add coin
			*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.
				// Add coin
				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()
{
	$task = new Combination();
	$coins = array(5, 7, 4, 2, 3);
	$n = count($coins);
	// Test A
	// x = 27
	$task->minimumCoin($coins, $n, 27);
	// Test B
	// x = 13
	$task->minimumCoin($coins, $n, 13);
	// Test C
	// x = 21
	$task->minimumCoin($coins, $n, 21);
	// Test D
	// x = 36
	$task->minimumCoin($coins, $n, 36);
	// Test E
	// x = 36
	$task->minimumCoin($coins, $n, 22);
}
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.
				// Add coin
				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 task = new Combination();
	var coins = [5, 7, 4, 2, 3];
	var n = coins.length;
	// Test A
	// x = 27
	task.minimumCoin(coins, n, 27);
	// Test B
	// x = 13
	task.minimumCoin(coins, n, 13);
	// Test C
	// x = 21
	task.minimumCoin(coins, n, 21);
	// Test D
	// x = 36
	task.minimumCoin(coins, n, 36);
	// Test E
	// x = 36
	task.minimumCoin(coins, n, 22);
}
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.
				#  Add coin
				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() :
	task = Combination()
	coins = [5, 7, 4, 2, 3]
	n = len(coins)
	#  Test A
	#  x = 27
	task.minimumCoin(coins, n, 27)
	#  Test B
	#  x = 13
	task.minimumCoin(coins, n, 13)
	#  Test C
	#  x = 21
	task.minimumCoin(coins, n, 21)
	#  Test D
	#  x = 36
	task.minimumCoin(coins, n, 36)
	#  Test E
	#  x = 36
	task.minimumCoin(coins, n, 22)

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.
				#  Add coin
				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() 
	task = Combination.new()
	coins = [5, 7, 4, 2, 3]
	n = coins.length
	#  Test A
	#  x = 27
	task.minimumCoin(coins, n, 27)
	#  Test B
	#  x = 13
	task.minimumCoin(coins, n, 13)
	#  Test C
	#  x = 21
	task.minimumCoin(coins, n, 21)
	#  Test D
	#  x = 36
	task.minimumCoin(coins, n, 36)
	#  Test E
	#  x = 36
	task.minimumCoin(coins, n, 22)
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.
				// Add coin
				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
		task.minimumCoin(coins, n, 27);
		// Test B
		// x = 13
		task.minimumCoin(coins, n, 13);
		// Test C
		// x = 21
		task.minimumCoin(coins, n, 21);
		// Test D
		// x = 36
		task.minimumCoin(coins, n, 36);
		// Test E
		// x = 36
		task.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
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.
				// Add coin
				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 task: Combination = Combination();
	let coins: [Int] = [5, 7, 4, 2, 3];
	let n: Int = coins.count;
	// Test A
	// x = 27
	task.minimumCoin(coins, n, 27);
	// Test B
	// x = 13
	task.minimumCoin(coins, n, 13);
	// Test C
	// x = 21
	task.minimumCoin(coins, n, 21);
	// Test D
	// x = 36
	task.minimumCoin(coins, n, 36);
	// Test E
	// x = 36
	task.minimumCoin(coins, n, 22);
}
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.
				// Add coin
				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 task: Combination = Combination();
	val coins: Array < Int > = arrayOf(5, 7, 4, 2, 3);
	val n: Int = coins.count();
	// Test A
	// x = 27
	task.minimumCoin(coins, n, 27);
	// Test B
	// x = 13
	task.minimumCoin(coins, n, 13);
	// Test C
	// x = 21
	task.minimumCoin(coins, n, 21);
	// Test D
	// x = 36
	task.minimumCoin(coins, n, 36);
	// Test E
	// x = 36
	task.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

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.

New Comment





Categories
Relative Post