Skip to content
Related Articles

Related Articles

Coin Change | DP-7

View Discussion
Improve Article
Save Article
  • Difficulty Level : Hard
  • Last Updated : 01 Sep, 2022
View Discussion
Improve Article
Save Article

Given a value sum, if we want to make change for sum cents, and we have an infinite supply of each of coins[] = { coins1, coins2, .. , coinsn} valued coins, how many ways can we make the change? The order of coins doesn’t matter.

Examples: 

Input: sum = 4, coins[] = {1,2,3}, 
Output: 4
Explanation: there are four solutions: {1, 1, 1, 1}, {1, 1, 2}, {2, 2}, {1, 3}. 

Input: sum = 10, coins[] = {2, 5, 3, 6}
Output: 5
Explanation: There are five solutions: 
{2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}.

Recommended Practice

1) Optimal Substructure: To count the total number of solutions, we can divide all set solutions into two sets. 

  • Solutions that do not contain nth coin (or coins[n-1]). 
  • Solutions that contain at least one occurrence of the nth coin (or coins[n-1]). 

Let count(coins[], n, sum) be the function to count the number of solutions, then it can be written as sum of count(coins[], n-1, sum) and count(coins[], n, sum-coins[n-1]).
Therefore, the problem has optimal substructure property as the problem can be solved using solutions to subproblems. 

2) Overlapping Subproblems: Following is a simple recursive implementation of the Coin Change problem. The implementation simply follows the recursive structure mentioned above.

3) Approach (Algorithm): See, here each coin of a given denomination can come an infinite number of times. (Repetition allowed), this is what we call UNBOUNDED KNAPSACK. We have 2 choices for a coin of a particular denomination, either i) to include, or ii) to exclude.  But here, the inclusion process is not for just once; we can include any denomination any number of times until sum<0.

Basically, If we are at coins[n-1], we can take as many instances of that coin ( unbounded inclusion ) i.e count(coins, n, sum – coins[n-1] ); then we move to coins[n-2]. After moving to coins[n-2], we can’t move back and can’t make choices for coins[n-1] i.e count(coins, n-1, sum).

Finally, as we have to find the total number of ways, so we will add these 2 possible choices, i.e count(coins, n, sum – coins[n-1] ) + count(coins, n-1, sum ); which will be our required answer.

C++




// Recursive C++ program for
// coin change problem.
#include <bits/stdc++.h>
using namespace std;
 
// Returns the count of ways we can
// sum coins[0...n-1] coins to get sum "sum"
int count(int coins[], int n, int sum)
{
     
    // If sum is 0 then there is 1 solution
    // (do not include any coin)
    if (sum == 0)
        return 1;
     
    // If sum is less than 0 then no
    // solution exists
    if (sum < 0)
        return 0;
 
    // If there are no coins and sum
    // is greater than 0, then no
    // solution exist
    if (n <= 0)
        return 0;
 
    // count is sum of solutions (i)
    // including coins[n-1] (ii) excluding coins[n-1]
    return count(coins, n - 1, sum) +
           count(coins, n, sum - coins[n - 1]);
}
 
// Driver code
int main()
{
    int i, j;
    int coins[] = { 1, 2, 3 };
    int n = sizeof(coins) / sizeof(coins[0]);
    int sum = 4;
     
    cout << " " << count(coins, n, sum);
     
    return 0;
}
 
// This code is contributed by shivanisinghss2110

C




// Recursive C program for
// coin change problem.
#include <stdio.h>
 
// Returns the count of ways we can
// sum coins[0...n-1] coins to get sum "sum"
int count(int coins[], int n, int sum)
{
    // If sum is 0 then there is 1 solution
    // (do not include any coin)
    if (sum == 0)
        return 1;
 
    // If sum is less than 0 then no
    // solution exists
    if (sum < 0)
        return 0;
 
    // If there are no coins and sum
    // is greater than 0, then no
    // solution exist
    if (n <= 0)
        return 0;
 
    // count is sum of solutions (i)
    // including coins[n-1] (ii) excluding coins[n-1]
    return count(coins, n - 1, sum)
           + count(coins, n, sum - coins[n - 1]);
}
 
// Driver program to test above function
int main()
{
    int i, j;
    int coins[] = { 1, 2, 3 };
    int n = sizeof(coins) / sizeof(coins[0]);
    printf("%d ", count(coins, n, 4));
    getchar();
    return 0;
}

Java




// Recursive JAVA program for
// coin change problem.
import java.util.*;
class GFG {
 
    // Returns the count of ways we can
    // sum coins[0...n-1] coins to get sum "sum"
    static int count(int coins[], int n, int sum)
    {
 
        // If sum is 0 then there is 1 solution
        // (do not include any coin)
        if (sum == 0)
            return 1;
 
        // If sum is less than 0 then no
        // solution exists
        if (sum < 0)
            return 0;
 
        // If there are no coins and sum
        // is greater than 0, then no
        // solution exist
        if (n <= 0)
            return 0;
 
        // count is sum of solutions (i)
        // including coins[n-1] (ii) excluding coins[n-1]
        return count(coins, n - 1, sum)
            + count(coins, n, sum - coins[n - 1]);
    }
 
    // Driver code
    public static void main(String args[])
    {
        int coins[] = { 1, 2, 3 };
        int n = coins.length;
 
        System.out.println(count(coins, n, 4));
    }
}
 
// This code is contributed by jyoti369

Python3




# Recursive Python3 program for
# coin change problem.
 
# Returns the count of ways we can sum
# coins[0...n-1] coins to get sum "sum"
def count(coins, n, sum):
 
    # If sum is 0 then there is 1
    # solution (do not include any coin)
    if (sum == 0):
        return 1
 
    # If sum is less than 0 then no
    # solution exists
    if (sum < 0):
        return 0
 
    # If there are no coins and sum
    # is greater than 0, then no
    # solution exist
    if (n <= 0):
        return 0
 
    # count is sum of solutions (i)
    # including coins[n-1] (ii) excluding coins[n-1]
    return count(coins, n - 1, sum) + count(coins, n, sum-coins[n-1])
 
 
# Driver program to test above function
coins = [1, 2, 3]
n = len(coins)
print(count(coins, n, 4))
 
# This code is contributed by Smitha Dinesh Semwal

C#




// Recursive C# program for
// coin change problem.
using System;
 
class GFG {
    // Returns the count of ways we can
    // sum coins[0...n-1] coins to get sum "sum"
    static int count(int[] coins, int n, int sum)
    {
        // If sum is 0 then there is 1 solution
        // (do not include any coin)
        if (sum == 0)
            return 1;
 
        // If sum is less than 0 then no
        // solution exists
        if (sum < 0)
            return 0;
 
        // If there are no coins and sum
        // is greater than 0, then no
        // solution exist
        if (n <= 0)
            return 0;
 
        // count is sum of solutions (i)
        // including coins[n-1] (ii) excluding coins[n-1]
        return count(coins, n - 1, sum)
            + count(coins, n, sum - coins[n - 1]);
    }
 
    // Driver program
    public static void Main()
    {
 
        int[] coins = { 1, 2, 3 };
        int n = coins.Length;
        Console.Write(count(coins, n, 4));
    }
}
// This code is contributed by Sam007

PHP




<?php
// Recursive PHP program for
// coin change problem.
 
// Returns the count of ways we can
// sum coins[0...n-1] coins to get sum "sum"
function coun($coins, $n, $sum)
{
     
    // If sum is 0 then there is
    // 1 solution (do not include
    // any coin)
    if ($sum == 0)
        return 1;
     
    // If sum is less than 0 then no
    // solution exists
    if ($sum < 0)
        return 0;
 
    // If there are no coins and sum
    // is greater than 0, then no
    // solution exist
    if ($n <= 0)
        return 0;
 
    // count is sum of solutions (i)
    // including coins[n-1] (ii) excluding coins[n-1]
    return coun($coins, $n - 1,$sum ) +
           coun($coins, $n, $sum - $coins[$n - 1] );
}
 
    // Driver Code
    $coins = array(1, 2, 3);
    $n = count($coins);
    echo coun($coins, $n, 4);
     
// This code is contributed by Sam007
?>

Javascript




<script>
// Recursive javascript program for
// coin change problem.
    
// Returns the count of ways we can
// sum coins[0...n-1] coins to get sum "sum"
function count(coins , n , sum )
{
 
    // If sum is 0 then there is 1 solution
    // (do not include any coin)
    if (sum == 0)
        return 1;
     
    // If sum is less than 0 then no
    // solution exists
    if (sum < 0)
        return 0;
 
    // If there are no coins and sum
    // is greater than 0, then no
    // solution exist
    if (n <=0)
        return 0;
 
    // count is sum of solutions (i)
    // including coins[n-1] (ii) excluding coins[n-1]
    return count( coins, n - 1, sum ) +
           count( coins, n, sum - coins[n - 1] );
}
 
// Driver program to test above function
var coins = [1, 2, 3];
var n = coins.length;
document.write( count(coins, n, 4));
 
// This code is contributed by Amit Katiyar
</script>

Output

 4

Time Complexity: O(2sum)

Auxiliary Space: O(target)

It should be noted that the above function computes the same subproblems again and again. See the following recursion tree for coins[] = {1, 2, 3} and n = 5. 

The function C({1}, 3) is called two times. If we draw the complete tree, then we can see that there are many subproblems being called more than once.  

C() --> count()
                             C({1,2,3}, 5)                     
                           /             \    
                         /                 \                  
             C({1,2,3}, 2)                 C({1,2}, 5)
            /       \                      /      \         
           /         \                    /         \   
C({1,2,3}, -1)  C({1,2}, 2)        C({1,2}, 3)    C({1}, 5)
               /    \             /     \           /     \
             /       \           /       \         /        \
    C({1,2},0)  C({1},2)   C({1,2},1) C({1},3)    C({1}, 4)  C({}, 5)
                   / \     / \        /\         /     \         
                  /   \   /   \     /   \       /       \  
                .      .  .     .   .     .   C({1}, 3) C({}, 4)
                                               / \ 
                                              /   \   
                                             .      .

Since same sub-problems are called again, this problem has the Overlapping Subproblems property. So the Coin Change problem has both properties (see this and this) of a dynamic programming problem. Like other typical Dynamic Programming(DP) problems, recomputations of the same subproblems can be avoided by constructing a temporary array table[][] in bottom-up manner.

Dynamic Programming Solution  

C++




// C++ program for coin change problem
 
#include <bits/stdc++.h>
 
using namespace std;
 
int count(int coins[], int n, int sum)
{
    int i, j, x, y;
 
    // We need sum+1 rows as the table
    // is constructed in bottom up
    // manner using the base case 0
    // value case (sum = 0)
    int table[sum + 1][n];
 
    // Fill the entries for 0
    // value case (sum = 0)
    for (i = 0; i < n; i++)
        table[0][i] = 1;
 
    // Fill rest of the table entries
    // in bottom up manner
    for (i = 1; i < sum + 1; i++) {
        for (j = 0; j < n; j++) {
            // Count of solutions including coins[j]
            x = (i - coins[j] >= 0) ? table[i - coins[j]][j]
                                    : 0;
 
            // Count of solutions excluding coins[j]
            y = (j >= 1) ? table[i][j - 1] : 0;
 
            // total count
            table[i][j] = x + y;
        }
    }
    return table[sum][n - 1];
}
 
// Driver Code
int main()
{
    int coins[] = { 1, 2, 3 };
    int n = sizeof(coins) / sizeof(coins[0]);
    int sum = 4;
    cout << count(coins, n, sum);
    return 0;
}
 
// This code is contributed
// by Akanksha Rai(Abby_akku)

C




// C program for coin change problem.
#include <stdio.h>
 
int count(int coins[], int n, int sum)
{
    int i, j, x, y;
 
    // We need sum+1 rows as the table is constructed
    // in bottom up manner using the base case 0
    // value case (sum = 0)
    int table[sum + 1][n];
 
    // Fill the entries for 0 value case (n = 0)
    for (i = 0; i < n; i++)
        table[0][i] = 1;
 
    // Fill rest of the table entries in bottom
    // up manner
    for (i = 1; i < sum + 1; i++) {
        for (j = 0; j < n; j++) {
            // Count of solutions including S[j]
            x = (i - coins[j] >= 0) ? table[i - coins[j]][j]
                                    : 0;
 
            // Count of solutions excluding S[j]
            y = (j >= 1) ? table[i][j - 1] : 0;
 
            // total count
            table[i][j] = x + y;
        }
    }
    return table[sum][n - 1];
}
 
// Driver program to test above function
int main()
{
    int coins[] = { 1, 2, 3 };
    int n = sizeof(coins) / sizeof(coins[0]);
    int sum = 4;
    printf(" %d ", count(coins, n, sum));
    return 0;
}

Java




/* Dynamic Programming Java implementation of Coin
   Change problem */
import java.util.Arrays;
 
class CoinChange {
    static long countWays(int coins[], int n, int sum)
    {
        // Time complexity of this function: O(n*sum)
        // Space Complexity of this function: O(sum)
 
        // table[i] will be storing the number of solutions
        // for value i. We need sum+1 rows as the table is
        // constructed in bottom up manner using the base
        // case (sum = 0)
        long[] table = new long[sum + 1];
 
        // Initialize all table values as 0
        Arrays.fill(table, 0);
 
        // Base case (If given value is 0)
        table[0] = 1;
 
        // Pick all coins one by one and update the table[]
        // values after the index greater than or equal to
        // the value of the picked coin
        for (int i = 0; i < n; i++)
            for (int j = coins[i]; j <= sum; j++)
                table[j] += table[j - coins[i]];
 
        return table[sum];
    }
 
    // Driver Function to test above function
    public static void main(String args[])
    {
        int coins[] = { 1, 2, 3 };
        int n = coins.length;
        int sum = 4;
        System.out.println(countWays(coins, n, sum));
    }
}
// This code is contributed by Pankaj Kumar

Python




# Dynamic Programming Python implementation of Coin
# Change problem
 
 
def count(coins, n, sum):
    # We need sum+1 rows as the table is constructed
    # in bottom up manner using the base case 0 value
    # case (sum = 0)
    table = [[0 for x in range(n)] for x in range(sum+1)]
 
    # Fill the entries for 0 value case (n = 0)
    for i in range(n):
        table[0][i] = 1
 
    # Fill rest of the table entries in bottom up manner
    for i in range(1, sum+1):
        for j in range(n):
 
            # Count of solutions including coins[j]
            x = table[i - coins[j]][j] if i-coins[j] >= 0 else 0
 
            # Count of solutions excluding coins[j]
            y = table[i][j-1] if j >= 1 else 0
 
            # total count
            table[i][j] = x + y
 
    return table[sum][n-1]
 
 
# Driver program to test above function
if __name__ == '__main__':
    coins = [1, 2, 3]
    n = len(coins)
    sum = 4
    print(count(coins, n, sum))
 
# This code is contributed by Bhavya Jain

C#




/* Dynamic Programming C# implementation of Coin
Change problem */
using System;
 
class GFG {
    static long countWays(int[] coins, int n, int sum)
    {
        // table[i] will be storing the number of solutions
        // for value i. We need sum+1 rows as the table is
        // constructed in bottom up manner using the base
        // case (sum = 0)
        int[] table = new int[sum + 1];
 
        // Initialize all table values as 0
        for (int i = 0; i < table.Length; i++) {
            table[i] = 0;
        }
 
        // Base case (If given value is 0)
        table[0] = 1;
 
        // Pick all coins one by one and update the table[]
        // values after the index greater than or equal to
        // the value of the picked coin
        for (int i = 0; i < n; i++)
            for (int j = coins[i]; j <= sum; j++)
                table[j] += table[j - coins[i]];
 
        return table[sum];
    }
 
    // Driver Function
    public static void Main()
    {
        int[] coins = { 1, 2, 3 };
        int n = coins.Length;
        int sum = 4;
        Console.Write(countWays(coins, n, sum));
    }
}
// This code is contributed by Sam007

PHP




<?php
// PHP program for
// coin change problem.
 
function count1($coins, $n, $sum)
{
    // We need sum+1 rows as
    // the table is constructed
    // in bottom up manner
    // using the base case 0
    // value case (sum = 0)
    $table;
    for ($i = 0; $i < $sum + 1; $i++)
    for ($j = 0; $j < $n; $j++)
        $table[$i][$j] = 0;
     
    // Fill the entries for
    // 0 value case (n = 0)
    for ($i = 0; $i < $n; $i++)
        $table[0][$i] = 1;
 
    // Fill rest of the table
    // entries in bottom up manner
    for ($i = 1; $i < $sum + 1; $i++)
    {
        for ($j = 0; $j < $n; $j++)
        {
            // Count of solutions
            // including coins[j]
            $x = ($i-$coins[$j] >= 0) ?
                  $table[$i - $coins[$j]][$j] : 0;
 
            // Count of solutions
            // excluding S[j]
            $y = ($j >= 1) ?
                  $table[$i][$j - 1] : 0;
 
            // total count
            $table[$i][$j] = $x + $y;
        }
    }
    return $table[$sum][$n-1];
}
 
// Driver Code
$coins = array(1, 2, 3);
$n = count($coins);
$sum = 4;
echo count1($coins, $n, $sum);
 
// This code is contributed by mits
?>

Javascript




<script>
 
/* Dynamic Programming javascript implementation of Coin
   Change problem */
 
function countWays(S , m , n)
{
    // table[i] will be storing the number of solutions
    // for value i. We need sum+1 rows as the table is
    // constructed in bottom up manner using the base
    // case (sum = 0)
    // Initialize all table values as 0
    var table = Array(sum+1).fill(0);
     
 
    // Base case (If given value is 0)
    table[0] = 1;
 
    // Pick all coins one by one and update the table
    // values after the index greater than or equal to
    // the value of the picked coin
    for (i=0; i<n; i++)
        for (j=coins[i]; j<=sum; j++)
            table[j] += table[j-coins[i]];
 
    return table[sum];
}
 
// Driver Function to test above function
var coins = [1, 2, 3];
var n = coins.length;
var sum = 4;
document.write(countWays(coins, n, sum));
 
// This code is contributed by 29AjayKumar
 
</script>

Output

4

Time Complexity: O(M*sum)
Auxiliary Space: O(M*sum)
 

Following is a simplified version of method 2. The auxiliary space required here is O(sum) only. 

C++




int count(int coins[], int n, int sum)
{
    // table[i] will be storing the number of solutions for
    // value i. We need sum+1 rows as the table is constructed
    // in bottom up manner using the base case (sum = 0)
    int table[sum + 1];
   
    // Initialize all table values as 0
    memset(table, 0, sizeof(table));
   
    // Base case (If given value is 0)
    table[0] = 1;
   
    // Pick all coins one by one and update the table[]
    // values after the index greater than or equal to the
    // value of the picked coin
    for (int i = 0; i < n; i++)
        for (int j = coins[i]; j <= sum; j++)
            table[j] += table[j - coins[i]];
    return table[sum];
}

Java




public static int count(int coins[], int n, int sum)
{
    // table[i] will be storing the number of solutions for
    // value i. We need sum+1 rows as the table is constructed
    // in bottom up manner using the base case (sum = 0)
    int table[] = new int[sum + 1];
 
    // Base case (If given value is 0)
    table[0] = 1;
 
    // Pick all coins one by one and update the table[]
    // values after the index greater than or equal to the
    // value of the picked coin
    for (int i = 0; i < n; i++)
        for (int j = coins[i]; j <= sum; j++)
            table[j] += table[j - coins[i]];
 
    return table[sum];
}

Python




# Dynamic Programming Python implementation of Coin
# Change problem
def count(coins, n, sum):
 
    # table[i] will be storing the number of solutions for
    # value i. We need sum+1 rows as the table is constructed
    # in bottom up manner using the base case (sum = 0)
    # Initialize all table values as 0
    table = [0 for k in range(sum+1)]
 
    # Base case (If given value is 0)
    table[0] = 1
 
    # Pick all coins one by one and update the table[] values
    # after the index greater than or equal to the value of the
    # picked coin
    for i in range(0, n):
        for j in range(coins[i], sum+1):
            table[j] += table[j-coins[i]]
 
    return table[sum]
 
 
# Driver program to test above function
coins = [1, 2, 3]
n = len(coins)
sum = 4
x = count(coins, n, sum)
print(x)
 
# This code is contributed by Afzal Ansari

C#




// Dynamic Programming C# implementation
// of Coin Change problem
using System;
 
class GFG {
    static int count(int[] coins, int n, int sum)
    {
        // table[i] will be storing the
        // number of solutions for value i.
        // We need sum+1 rows as the table
        // is constructed in bottom up manner
        // using the base case (sum = 0)
        int[] table = new int[sum + 1];
 
        // Base case (If given value is 0)
        table[0] = 1;
 
        // Pick all coins one by one and
        // update the table[] values after
        // the index greater than or equal
        // to the value of the picked coin
        for (int i = 0; i < n; i++)
            for (int j = coins[i]; j <= sum; j++)
                table[j] += table[j - coins[i]];
 
        return table[sum];
    }
 
    // Driver Code
    public static void Main()
    {
        int[] coins = { 1, 2, 3 };
        int n = coins.Length;
        int sum = 4;
        Console.Write(count(coins, n, sum));
    }
}
 
// This code is contributed by Raj

PHP




<?php
function count_1( &$coins, $n, $sum )
{
    // table[i] will be storing the number
    // of solutions for value i. We need sum+1
    // rows as the table is constructed in
    // bottom up manner using the base case (sum = 0)
    $table = array_fill(0, $sum + 1, NULl);
 
    // Base case (If given value is 0)
    $table[0] = 1;
 
    // Pick all coins one by one and update
    // the table[] values after the index
    // greater than or equal to the value
    // of the picked coin
    for($i = 0; $i < $n; $i++)
        for($j = $coins[$i]; $j <= $sum; $j++)
            $table[$j] += $table[$j - $coins[$i]];
 
    return $table[$sum];
}
 
// Driver Code
$coins = array(1, 2, 3);
$n = sizeof($coins);
$sum = 4;
$x = count_1($coins, $n, $sum);
echo $x;
 
// This code is contributed
// by ChitraNayal
?>

Javascript




<script>
    // Dynamic Programming Javascript implementation
    // of Coin Change problem
       
    function count(coins, n, sum)
    {
        // table[i] will be storing the
        // number of solutions for value i.
        // We need n+1 rows as the table
        // is constructed in bottom up manner
        // using the base case (sum = 0)
        let table = new Array(sum + 1);
        table.fill(0);
 
        // Base case (If given value is 0)
        table[0] = 1;
 
        // Pick all coins one by one and
        // update the table[] values after
        // the index greater than or equal
        // to the value of the picked coin
        for(let i = 0; i < n; i++)
            for(let j = coins[i]; j <= sum; j++)
                table[j] += table[j - coins[i]];
 
        return table[sum];
    }
     
    let coins = [1, 2, 3];
    let n = coins.length;
    let sum = 4;
    document.write(count(coins, n, sum));
</script>

Output: 

4

Time Complexity: O(M*sum)

Auxiliary Space: O(sum)

Following is another Top Down DP Approach using memoization:

C++




#include <bits/stdc++.h>
using namespace std;
 
int coinchange(vector<int>& a, int v, int n,
               vector<vector<int> >& dp)
{
    if (v == 0)
        return dp[n][v] = 1;
    if (n == 0)
        return 0;
    if (dp[n][v] != -1)
        return dp[n][v];
    if (a[n - 1] <= v) {
        // Either Pick this coin or not
        return dp[n][v] = coinchange(a, v - a[n - 1], n, dp)
                          + coinchange(a, v, n - 1, dp);
    }
    else // We have no option but to leave this coin
        return dp[n][v] = coinchange(a, v, n - 1, dp);
}
int32_t main()
{
    int tc = 1;
    // cin >> tc;
    while (tc--) {
        int n, v;
        n = 3, v = 4;
        vector<int> a = { 1, 2, 3 };
        vector<vector<int> > dp(n + 1,
                                vector<int>(v + 1, -1));
        int res = coinchange(a, v, n, dp);
        cout << res << endl;
    }
}
// This Code is Contributed by
// Harshit Agrawal NITT

Java




// Java program for the above approach
import java.util.*;
 
class GFG {
 
    static int coinchange(int[] a, int v, int n, int[][] dp)
    {
        if (v == 0)
            return dp[n][v] = 1;
        if (n == 0)
            return 0;
        if (dp[n][v] != -1)
            return dp[n][v];
        if (a[n - 1] <= v)
        {
           
            // Either Pick this coin or not
            return dp[n][v]
                = coinchange(a, v - a[n - 1], n, dp)
                  + coinchange(a, v, n - 1, dp);
        }
        else // We have no option but to leave this coin
            return dp[n][v] = coinchange(a, v, n - 1, dp);
    }
 
  // Driver code
    public static void main(String[] args)
    {
        int tc = 1;
        while (tc != 0) {
            int n, v;
            n = 3;
            v = 4;
            int[] a = { 1, 2, 3 };
            int[][] dp = new int[n + 1][v + 1];
            for (int[] row : dp)
                Arrays.fill(row, -1);
            int res = coinchange(a, v, n, dp);
            System.out.println(res);
            tc--;
        }
    }
}
 
// This code is contributed by rajsanghavi9.

Python3




# Python program for the above approach
def coinchange(a, v, n, dp):
    if (v == 0):
        dp[n][v] = 1;
        return dp[n][v];
    if (n == 0):
        return 0;
    if (dp[n][v] != -1):
        return dp[n][v];
    if (a[n - 1] <= v):
 
        # Either Pick this coin or not
        dp[n][v] = coinchange(a, v - a[n - 1], n, dp) + coinchange(a, v, n - 1, dp);
        return dp[n][v];
    else: # We have no option but to leave this coin
        dp[n][v] = coinchange(a, v, n - 1, dp);
        return dp[n][v];
 
# Driver code
if __name__ == '__main__':
    tc = 1;
    while (tc != 0):
        n = 3;
        v = 4;
        a = [ 1, 2, 3 ];
        dp = [[-1 for i in range(v+1)] for j in range(n+1)]
        res = coinchange(a, v, n, dp);
        print(res);
        tc -= 1;
     
# This code is contributed by Rajput-Ji

C#




// C# program for the above approach
using System;
public class GFG {
 
    static int coinchange(int[] a, int v, int n, int[, ] dp)
    {
        if (v == 0)
            return dp[n, v] = 1;
        if (n == 0)
            return 0;
        if (dp[n, v] != -1)
            return dp[n, v];
        if (a[n - 1] <= v) {
 
            // Either Pick this coin or not
            return dp[n, v]
                = coinchange(a, v - a[n - 1], n, dp)
                  + coinchange(a, v, n - 1, dp);
        }
        else // We have no option but to leave this coin
            return dp[n, v] = coinchange(a, v, n - 1, dp);
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        int tc = 1;
        while (tc != 0) {
            int n, v;
            n = 3;
            v = 4;
            int[] a = { 1, 2, 3 };
            int[, ] dp = new int[n + 1, v + 1];
            for (int j = 0; j < n + 1; j++) {
                for (int l = 0; l < v + 1; l++)
                    dp[j, l] = -1;
            }
            int res = coinchange(a, v, n, dp);
            Console.WriteLine(res);
            tc--;
        }
    }
}
 
// This code is contributed by umadevi9616

Javascript




<script>
// javascript program for the above approach
 
    function coinchange(a , v , n,  dp) {
        if (v == 0)
            return dp[n][v] = 1;
        if (n == 0)
            return 0;
        if (dp[n][v] != -1)
            return dp[n][v];
        if (a[n - 1] <= v) {
 
            // Either Pick this coin or not
            return dp[n][v] = coinchange(a, v - a[n - 1], n, dp) + coinchange(a, v, n - 1, dp);
        } else // We have no option but to leave this coin
            return dp[n][v] = coinchange(a, v, n - 1, dp);
    }
 
    // Driver code
     
        var tc = 1;
        while (tc != 0) {
            var n, v;
            n = 3;
            v = 4;
            var a = [ 1, 2, 3 ];
            var dp = Array(n+1).fill().map(() => Array(v+1).fill(-1));
             
            var res = coinchange(a, v, n, dp);
            document.write(res);
            tc--;
        }
 
// This code contributed by umadevi9616
</script>

Output

4

Time Complexity: O(M*sum)

Auxiliary Space: O(M*sum)

This article is contributed by: Mayukh Sinha. Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above.


My Personal Notes arrow_drop_up
Recommended Articles
Page :

Start Your Coding Journey Now!