Generate a combination of minimum coins that sums to a given value | Javascript 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 INT_MAX 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
var MAX = 100000 ; var dp = Array ( MAX + 1 ) ; var denomination = [ ] ; function countMinCoins ( n , C , m ) { if ( n == 0 ) { dp [ 0 ] = 0 ; return 0 ; } if ( dp [ n ] != - 1 ) return dp [ n ] ; var ret = 1000000000 ; for ( var i = 0 ; i < m ; i ++ ) { if ( C [ i ] <= n ) { var x = countMinCoins ( n - C [ i ] , C , m ) ; if ( x != 1000000000 ) ret = Math . min ( ret , 1 + x ) ; } } dp [ n ] = ret ; return ret ; } function findSolution ( n , C , m ) { if ( n == 0 ) { denomination . forEach ( it => { document . write ( it + ' ' ) ; } ) ; return ; } for ( var i = 0 ; i < m ; i ++ ) { if ( n - C [ i ] >= 0 && dp [ n - C [ i ] ] + 1 == dp [ n ] ) { denomination . push ( C [ i ] ) ; findSolution ( n - C [ i ] , C , m ) ; break ; } } } function countMinCoinsUtil ( X , C , N ) { dp = Array ( MAX + 1 ) . fill ( - 1 ) ; var isPossible = countMinCoins ( X , C , N ) ; if ( isPossible == 1000000000 ) { document . write ( " " ) ; } else { findSolution ( X , C , N ) ; } } var X = 21 ; var arr = [ 2 , 3 , 4 , 5 ] ; var N = arr . length ; countMinCoinsUtil ( X , arr , N ) ;