Generate a combination of minimum coins that sums to a given value | Java program for the above approach ; dp array to memoize the results ; List to store the result ; Function to find the minimum number of coins to make the sum equals to X ; Base case ; If previously computed subproblem occurred ; Initialize result ; Try every coin that has smaller value than n ; Check for Integer . MAX_VALUE to avoid overflow and see if result can be minimized ; Memoizing value of current state ; Function to find the possible combination of coins to make the sum equal to X ; Base Case ; Print Solutions ; Try every coin that has value smaller than n ; Add current denominations ; Backtrack ; Function to find the minimum combinations of coins for value X ; Initialize dp with - 1 ; Min coins ; If no solution exists ; Backtrack to find the solution ; Driver code ; Set of possible denominations ; Function Call
import java . util . * ; class GFG { static final int MAX = 100000 ; static int [ ] dp = new int [ MAX + 1 ] ; static List < Integer > denomination = new LinkedList < Integer > ( ) ; static int countMinCoins ( int n , int C [ ] , int m ) { if ( n == 0 ) { dp [ 0 ] = 0 ; return 0 ; } if ( dp [ n ] != - 1 ) return dp [ n ] ; int ret = Integer . MAX_VALUE ; for ( int i = 0 ; i < m ; i ++ ) { if ( C [ i ] <= n ) { int x = countMinCoins ( n - C [ i ] , C , m ) ; if ( x != Integer . MAX_VALUE ) ret = Math . min ( ret , 1 + x ) ; } } dp [ n ] = ret ; return ret ; } static void findSolution ( int n , int C [ ] , int m ) { if ( n == 0 ) { for ( int it : denomination ) { System . out . print ( it + " ▁ " ) ; } return ; } for ( int i = 0 ; i < m ; i ++ ) { if ( n - C [ i ] >= 0 && dp [ n - C [ i ] ] + 1 == dp [ n ] ) { denomination . add ( C [ i ] ) ; findSolution ( n - C [ i ] , C , m ) ; break ; } } } static void countMinCoinsUtil ( int X , int C [ ] , int N ) { for ( int i = 0 ; i < dp . length ; i ++ ) dp [ i ] = - 1 ; int isPossible = countMinCoins ( X , C , N ) ; if ( isPossible == Integer . MAX_VALUE ) { System . out . print ( " - 1" ) ; } else { findSolution ( X , C , N ) ; } } public static void main ( String [ ] args ) { int X = 21 ; int arr [ ] = { 2 , 3 , 4 , 5 } ; int N = arr . length ; countMinCoinsUtil ( X , arr , N ) ; } }