Construct the largest number whose sum of cost of digits is K | Function to find the maximum number among the two numbers S and T ; If "0" exists in the string S ; If "0" exists in the string T ; Else return the maximum number formed ; Recursive function to find maximum number formed such that the sum of cost of digits of formed number is K ; Base Case ; Return the stored state ; Including the digit ( idx + 1 ) ; Excluding the digit ( idx + 1 ) ; Store the result and return ; Function to find the maximum number formed such that the sum of the cost digits in the formed number is K ; Stores all Dp - states ; Recursive Call ; Return the result ; Driver Code
def getMaximum ( S , T ) : NEW_LINE INDENT if ( S . count ( "0" ) > 0 ) : NEW_LINE INDENT return T ; NEW_LINE DEDENT if ( T . count ( "0" ) > 0 ) : NEW_LINE INDENT return S ; NEW_LINE DEDENT return S if len ( S ) > len ( T ) else T ; NEW_LINE DEDENT def recursion ( arr , idx , N , K , dp ) : NEW_LINE INDENT if ( K == 0 ) : NEW_LINE INDENT return " " ; NEW_LINE DEDENT if ( K < 0 or idx == N ) : NEW_LINE INDENT return "0" ; NEW_LINE DEDENT if ( dp [ idx ] [ K ] != " - 1" ) : NEW_LINE INDENT return dp [ idx ] [ K ] ; NEW_LINE DEDENT include = str ( idx + 1 ) + recursion ( arr , 0 , N , K - arr [ idx ] , dp ) ; NEW_LINE exclude = recursion ( arr , idx + 1 , N , K , dp ) ; NEW_LINE dp [ idx ] [ K ] = getMaximum ( include , exclude ) NEW_LINE return ( dp [ idx ] [ K ] ) NEW_LINE DEDENT def largestNumber ( arr , N , K ) : NEW_LINE INDENT dp = [ [ " - 1" for i in range ( K + 1 ) ] for i in range ( N + 1 ) ] NEW_LINE ans = recursion ( arr , 0 , N , K , dp ) ; NEW_LINE return "0" if ans == " " else ans ; NEW_LINE DEDENT arr = [ 3 , 12 , 9 , 5 , 3 , 4 , 6 , 5 , 10 ] ; NEW_LINE K = 14 ; NEW_LINE N = len ( arr ) ; NEW_LINE print ( largestNumber ( arr , N , K ) ) ; NEW_LINE