Generate a combination of minimum coins that sums to a given value | Python3 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 . an 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 ; Min coins ; If no solution exists ; Backtrack to find the solution ; Driver code ; Set of possible denominations ; Function call
import sys NEW_LINE MAX = 100000 NEW_LINE dp = [ - 1 ] * ( MAX + 1 ) NEW_LINE denomination = [ ] NEW_LINE def countMinCoins ( n , C , m ) : NEW_LINE INDENT if ( n == 0 ) : NEW_LINE INDENT dp [ 0 ] = 0 NEW_LINE return 0 NEW_LINE DEDENT if ( dp [ n ] != - 1 ) : NEW_LINE INDENT return dp [ n ] NEW_LINE DEDENT ret = sys . maxsize NEW_LINE for i in range ( m ) : NEW_LINE INDENT if ( C [ i ] <= n ) : NEW_LINE INDENT x = countMinCoins ( n - C [ i ] , C , m ) NEW_LINE if ( x != sys . maxsize ) : NEW_LINE INDENT ret = min ( ret , 1 + x ) NEW_LINE DEDENT DEDENT DEDENT dp [ n ] = ret NEW_LINE return ret NEW_LINE DEDENT def findSolution ( n , C , m ) : NEW_LINE INDENT if ( n == 0 ) : NEW_LINE INDENT for it in denomination : NEW_LINE INDENT print ( it , end = " ▁ " ) NEW_LINE DEDENT return NEW_LINE DEDENT for i in range ( m ) : NEW_LINE INDENT if ( n - C [ i ] >= 0 and dp [ n - C [ i ] ] + 1 == dp [ n ] ) : NEW_LINE INDENT denomination . append ( C [ i ] ) NEW_LINE findSolution ( n - C [ i ] , C , m ) NEW_LINE break NEW_LINE DEDENT DEDENT DEDENT def countMinCoinsUtil ( X , C , N ) : NEW_LINE INDENT isPossible = countMinCoins ( X , C , N ) NEW_LINE if ( isPossible == sys . maxsize ) : NEW_LINE INDENT print ( " - 1" ) NEW_LINE DEDENT else : NEW_LINE INDENT findSolution ( X , C , N ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT X = 21 NEW_LINE arr = [ 2 , 3 , 4 , 5 ] NEW_LINE N = len ( arr ) NEW_LINE countMinCoinsUtil ( X , arr , N ) NEW_LINE DEDENT