Coin change problem using recursion
The coin change problem is a classic problem in computer science and mathematics that involves finding the number of ways to make change for a given amount of money using a set of available coins. The problem can be solved using recursion, which is a programming technique that involves breaking down a problem into smaller sub-problems and solving them recursively.
We can solve this problem recursively by breaking it down into sub-problems. We start with the largest denomination coin and try to use as many of them as possible to make change for the given amount. Then we move on to the next largest denomination coin and repeat the process until we reach the smallest denomination coin.
Here's how the recursive solution works:
- If the amount is 0, there is only one way to make change - by using no coins.
- If the amount is less than 0 or we have no more coins to use, there are no ways to make change.
- Otherwise, we have two options: a. Use the largest denomination coin and reduce the amount by that denomination. The number of ways to make change is then the number of ways to make change for the reduced amount using the remaining coins. b. Do not use the largest denomination coin and move on to the next denomination coin. The number of ways to make change is then the number of ways to make change for the original amount using the remaining coins.
Code Example
// C program for
// Coin change problem using recursion
#include <stdio.h>
int count(int coins[], int size, int n)
{
if (n == 0)
{
// When n is zero
return 1;
}
else if (n < 0)
{
// When n is less than zero means no solution possible
return 0;
}
else if (size <= 0 && n >= 1)
{
// When size is zero and n is greater than 1
return 0;
}
// Count solution using recursion
return count(coins, size - 1, n) +
count(coins, size, n - coins[size - 1]);
}
int main(int argc, char
const *argv[])
{
// Assume given coins is positive number
int coins[] = {
7 , 1 , 5 , 2
};
// Get the number of coins
int size = sizeof(coins) / sizeof(coins[0]);
int n = 10;
/*
[1,1,1,1,1,1,1,1,1,1]
[1,1,1,1,1,1,1,1,2]
[1,1,1,1,1,1,2,2]
[1,1,1,1,2,2,2]
[1,1,2,2,2,2]
[2,2,2,2,2]
[1,1,1,7]
[1,2,7]
[1,1,1,1,1,5]
[1,1,1,2,5]
[1,2,2,5]
[5,5]
-------------------
12 solution
*/
int ans = count(coins, size, n);
// Display possible result
printf(" Result : %d \n", ans);
return 0;
}
input
Result : 12
// Include header file
#include <iostream>
using namespace std;
/*
C++ program
Coin change problem using recursion
*/
class Counting
{
public: int count(int coins[], int size, int n)
{
if (n == 0)
{
// When n is zero
return 1;
}
else if (n < 0)
{
// When n is less than zero means no solution possible
return 0;
}
else if (size <= 0 && n >= 1)
{
// When size is zero and n is greater than 1
return 0;
}
// Count solution using recursion
return this->count(coins, size - 1, n) + this->count(coins, size, n - coins[size - 1]);
}
};
int main()
{
Counting *task = new Counting();
// Assume given coins is positive number
int coins[] = {
7 , 1 , 5 , 2
};
// Get the number of coins
int size = sizeof(coins) / sizeof(coins[0]);
int n = 10;
/*
Target n : 10
----------------
[1,1,1,1,1,1,1,1,1,1]
[1,1,1,1,1,1,1,1,2]
[1,1,1,1,1,1,2,2]
[1,1,1,1,2,2,2]
[1,1,2,2,2,2]
[2,2,2,2,2]
[1,1,1,7]
[1,2,7]
[1,1,1,1,1,5]
[1,1,1,2,5]
[1,2,2,5]
[5,5]
-------------------
12 solution
*/
int ans = task->count(coins, size, n);
// Display possible result
cout << " Result : " << ans << " \n";
return 0;
}
input
Result : 12
/*
Java program
Coin change problem using recursion
*/
public class Counting
{
public int count(int[] coins, int size, int n)
{
if (n == 0)
{
// When n is zero
return 1;
}
else if (n < 0)
{
// When n is less than zero means no solution possible
return 0;
}
else if (size <= 0 && n >= 1)
{
// When size is zero and n is greater than 1
return 0;
}
// Count solution using recursion
return this.count(coins, size - 1, n) +
this.count(coins, size, n - coins[size - 1]);
}
public static void main(String[] args)
{
Counting task = new Counting();
// Assume given coins is positive number
int[] coins = {
7 , 1 , 5 , 2
};
// Get the number of coins
int size = coins.length;
int n = 10;
/*
[1,1,1,1,1,1,1,1,1,1]
[1,1,1,1,1,1,1,1,2]
[1,1,1,1,1,1,2,2]
[1,1,1,1,2,2,2]
[1,1,2,2,2,2]
[2,2,2,2,2]
[1,1,1,7]
[1,2,7]
[1,1,1,1,1,5]
[1,1,1,2,5]
[1,2,2,5]
[5,5]
-------------------
12 solution
*/
int ans = task.count(coins, size, n);
// Display possible result
System.out.print(" Result : " + ans + " \n");
}
}
input
Result : 12
// Include namespace system
using System;
/*
Csharp program
Coin change problem using recursion
*/
public class Counting
{
public int count(int[] coins, int size, int n)
{
if (n == 0)
{
// When n is zero
return 1;
}
else if (n < 0)
{
// When n is less than zero means no solution possible
return 0;
}
else if (size <= 0 && n >= 1)
{
// When size is zero and n is greater than 1
return 0;
}
// Count solution using recursion
return this.count(coins, size - 1, n) +
this.count(coins, size, n - coins[size - 1]);
}
public static void Main(String[] args)
{
Counting task = new Counting();
// Assume given coins is positive number
int[] coins = {
7 , 1 , 5 , 2
};
// Get the number of coins
int size = coins.Length;
int n = 10;
/*
Target n : 10
----------------
[1,1,1,1,1,1,1,1,1,1]
[1,1,1,1,1,1,1,1,2]
[1,1,1,1,1,1,2,2]
[1,1,1,1,2,2,2]
[1,1,2,2,2,2]
[2,2,2,2,2]
[1,1,1,7]
[1,2,7]
[1,1,1,1,1,5]
[1,1,1,2,5]
[1,2,2,5]
[5,5]
-------------------
12 solution
*/
int ans = task.count(coins, size, n);
// Display possible result
Console.Write(" Result : " + ans + " \n");
}
}
input
Result : 12
<?php
/*
Php program
Coin change problem using recursion
*/
class Counting
{
public function count($coins, $size, $n)
{
if ($n == 0)
{
// When n is zero
return 1;
}
else if ($n < 0)
{
// When n is less than zero means no solution possible
return 0;
}
else if ($size <= 0 && $n >= 1)
{
// When size is zero and n is greater than 1
return 0;
}
// Count solution using recursion
return $this->count($coins, $size - 1, $n) +
$this->count($coins, $size, $n - $coins[$size - 1]);
}
}
function main()
{
$task = new Counting();
// Assume given coins is positive number
$coins = array(7, 1, 5, 2);
// Get the number of coins
$size = count($coins);
$n = 10;
/*
Target n : 10
----------------
[1,1,1,1,1,1,1,1,1,1]
[1,1,1,1,1,1,1,1,2]
[1,1,1,1,1,1,2,2]
[1,1,1,1,2,2,2]
[1,1,2,2,2,2]
[2,2,2,2,2]
[1,1,1,7]
[1,2,7]
[1,1,1,1,1,5]
[1,1,1,2,5]
[1,2,2,5]
[5,5]
-------------------
12 solution
*/
$ans = $task->count($coins, $size, $n);
// Display possible result
echo(" Result : ".$ans.
" \n");
}
main();
input
Result : 12
/*
Node JS program
Coin change problem using recursion
*/
class Counting
{
count(coins, size, n)
{
if (n == 0)
{
// When n is zero
return 1;
}
else if (n < 0)
{
// When n is less than zero means no solution possible
return 0;
}
else if (size <= 0 && n >= 1)
{
// When size is zero and n is greater than 1
return 0;
}
// Count solution using recursion
return this.count(coins, size - 1, n) +
this.count(coins, size, n - coins[size - 1]);
}
}
function main()
{
var task = new Counting();
// Assume given coins is positive number
var coins = [7, 1, 5, 2];
// Get the number of coins
var size = coins.length;
var n = 10;
/*
Target n : 10
----------------
[1,1,1,1,1,1,1,1,1,1]
[1,1,1,1,1,1,1,1,2]
[1,1,1,1,1,1,2,2]
[1,1,1,1,2,2,2]
[1,1,2,2,2,2]
[2,2,2,2,2]
[1,1,1,7]
[1,2,7]
[1,1,1,1,1,5]
[1,1,1,2,5]
[1,2,2,5]
[5,5]
-------------------
12 solution
*/
var ans = task.count(coins, size, n);
// Display possible result
process.stdout.write(" Result : " + ans + " \n");
}
main();
input
Result : 12
# Python 3 program
# Coin change problem using recursion
class Counting :
def count(self, coins, size, n) :
if (n == 0) :
# When n is zero
return 1
elif (n < 0) :
# When n is less than zero means no solution possible
return 0
elif (size <= 0 and n >= 1) :
# When size is zero and n is greater than 1
return 0
# Count solution using recursion
return self.count(coins, size - 1, n) + self.count(
coins, size, n - coins[size - 1])
def main() :
task = Counting()
# Assume given coins is positive number
coins = [7, 1, 5, 2]
# Get the number of coins
size = len(coins)
n = 10
# Target n : 10
# ----------------
# [1,1,1,1,1,1,1,1,1,1]
# [1,1,1,1,1,1,1,1,2]
# [1,1,1,1,1,1,2,2]
# [1,1,1,1,2,2,2]
# [1,1,2,2,2,2]
# [2,2,2,2,2]
# [1,1,1,7]
# [1,2,7]
# [1,1,1,1,1,5]
# [1,1,1,2,5]
# [1,2,2,5]
# [5,5]
# -------------------
# 12 solution
ans = task.count(coins, size, n)
# Display possible result
print(" Result : ", ans ," ")
if __name__ == "__main__": main()
input
Result : 12
# Ruby program
# Coin change problem using recursion
class Counting
def count(coins, size, n)
if (n == 0)
# When n is zero
return 1
elsif (n < 0)
# When n is less than zero means no solution possible
return 0
elsif (size <= 0 && n >= 1)
# When size is zero and n is greater than 1
return 0
end
# Count solution using recursion
return self.count(coins, size - 1, n) +
self.count(coins, size, n - coins[size - 1])
end
end
def main()
task = Counting.new()
# Assume given coins is positive number
coins = [7, 1, 5, 2]
# Get the number of coins
size = coins.length
n = 10
# Target n : 10
# ----------------
# [1,1,1,1,1,1,1,1,1,1]
# [1,1,1,1,1,1,1,1,2]
# [1,1,1,1,1,1,2,2]
# [1,1,1,1,2,2,2]
# [1,1,2,2,2,2]
# [2,2,2,2,2]
# [1,1,1,7]
# [1,2,7]
# [1,1,1,1,1,5]
# [1,1,1,2,5]
# [1,2,2,5]
# [5,5]
# -------------------
# 12 solution
ans = task.count(coins, size, n)
# Display possible result
print(" Result : ", ans ," \n")
end
main()
input
Result : 12
/*
Scala program
Coin change problem using recursion
*/
class Counting()
{
def count(coins: Array[Int], size: Int, n: Int): Int = {
if (n == 0)
{
// When n is zero
return 1;
}
else if (n < 0)
{
// When n is less than zero means no solution possible
return 0;
}
else if (size <= 0 && n >= 1)
{
// When size is zero and n is greater than 1
return 0;
}
// Count solution using recursion
return this.count(coins, size - 1, n) +
this.count(coins, size, n - coins(size - 1));
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Counting = new Counting();
// Assume given coins is positive number
var coins: Array[Int] = Array(7, 1, 5, 2);
// Get the number of coins
var size: Int = coins.length;
var n: Int = 10;
/*
Target n : 10
----------------
[1,1,1,1,1,1,1,1,1,1]
[1,1,1,1,1,1,1,1,2]
[1,1,1,1,1,1,2,2]
[1,1,1,1,2,2,2]
[1,1,2,2,2,2]
[2,2,2,2,2]
[1,1,1,7]
[1,2,7]
[1,1,1,1,1,5]
[1,1,1,2,5]
[1,2,2,5]
[5,5]
-------------------
12 solution
*/
var ans: Int = task.count(coins, size, n);
// Display possible result
print(" Result : " + ans + " \n");
}
}
input
Result : 12
import Foundation;
/*
Swift 4 program
Coin change problem using recursion
*/
class Counting
{
func count(_ coins: [Int], _ size: Int, _ n: Int) -> Int
{
if (n == 0)
{
// When n is zero
return 1;
}
else if (n < 0)
{
// When n is less than zero means no solution possible
return 0;
}
else if (size <= 0 && n >= 1)
{
// When size is zero and n is greater than 1
return 0;
}
// Count solution using recursion
return self.count(coins, size - 1, n) +
self.count(coins, size, n - coins[size - 1]);
}
}
func main()
{
let task: Counting = Counting();
// Assume given coins is positive number
let coins: [Int] = [7, 1, 5, 2];
// Get the number of coins
let size: Int = coins.count;
let n: Int = 10;
/*
Target n : 10
----------------
[1,1,1,1,1,1,1,1,1,1]
[1,1,1,1,1,1,1,1,2]
[1,1,1,1,1,1,2,2]
[1,1,1,1,2,2,2]
[1,1,2,2,2,2]
[2,2,2,2,2]
[1,1,1,7]
[1,2,7]
[1,1,1,1,1,5]
[1,1,1,2,5]
[1,2,2,5]
[5,5]
-------------------
12 solution
*/
let ans: Int = task.count(coins, size, n);
// Display possible result
print(" Result : ", ans ," ");
}
main();
input
Result : 12
/*
Kotlin program
Coin change problem using recursion
*/
class Counting
{
fun count(coins: Array < Int > , size: Int, n: Int): Int
{
if (n == 0)
{
// When n is zero
return 1;
}
else if (n < 0)
{
// When n is less than zero means no solution possible
return 0;
}
else if (size <= 0 && n >= 1)
{
// When size is zero and n is greater than 1
return 0;
}
// Count solution using recursion
return this.count(coins, size - 1, n) +
this.count(coins, size, n - coins[size - 1]);
}
}
fun main(args: Array < String > ): Unit
{
val task: Counting = Counting();
// Assume given coins is positive number
val coins: Array < Int > = arrayOf(7, 1, 5, 2);
// Get the number of coins
val size: Int = coins.count();
val n: Int = 10;
/*
Target n : 10
----------------
[1,1,1,1,1,1,1,1,1,1]
[1,1,1,1,1,1,1,1,2]
[1,1,1,1,1,1,2,2]
[1,1,1,1,2,2,2]
[1,1,2,2,2,2]
[2,2,2,2,2]
[1,1,1,7]
[1,2,7]
[1,1,1,1,1,5]
[1,1,1,2,5]
[1,2,2,5]
[5,5]
-------------------
12 solution
*/
val ans: Int = task.count(coins, size, n);
// Display possible result
print(" Result : " + ans + " \n");
}
input
Result : 12
package main
import "fmt"
/*
Go program
Coin change problem using recursion
*/
func count(coins[] int, size int, n int) int {
if n == 0 {
// When n is zero
return 1
} else if n < 0 {
// When n is less than zero means no solution possible
return 0
} else if size <= 0 && n >= 1 {
// When size is zero and n is greater than 1
return 0
}
// Count solution using recursion
return count(coins, size - 1, n) + count(coins, size, n - coins[size - 1])
}
func main() {
// Assume given coins is positive number
var coins = [] int {
7,
1,
5,
2,
}
// Get the number of coins
var size int = len(coins)
var n int = 10
/*
Target n : 10
----------------
[1,1,1,1,1,1,1,1,1,1]
[1,1,1,1,1,1,1,1,2]
[1,1,1,1,1,1,2,2]
[1,1,1,1,2,2,2]
[1,1,2,2,2,2]
[2,2,2,2,2]
[1,1,1,7]
[1,2,7]
[1,1,1,1,1,5]
[1,1,1,2,5]
[1,2,2,5]
[5,5]
-------------------
12 solution
*/
var ans int = count(coins, size, n)
// Display possible result
fmt.Print(" Result : ", ans, " \n")
}
input
Result : 12
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