Construct the largest number whose sum of cost of digits is K | C ++ program for the above approach ; 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
#include " bits / stdc + + . h " NEW_LINE using namespace std ; string getMaximum ( string & S , string & T ) { if ( S . find ( "0" ) != string :: npos ) return T ; if ( T . find ( "0" ) != string :: npos ) return S ; return ( S . length ( ) > T . length ( ) ? S : T ) ; } string recursion ( int arr [ ] , int idx , int N , int K , vector < vector < string > > & dp ) { if ( K == 0 ) { return " " ; } if ( K < 0 or idx == N ) { return "0" ; } if ( dp [ idx ] [ K ] != " - 1" ) return dp [ idx ] [ K ] ; string include = to_string ( idx + 1 ) + recursion ( arr , 0 , N , K - arr [ idx ] , dp ) ; string exclude = recursion ( arr , idx + 1 , N , K , dp ) ; return dp [ idx ] [ K ] = getMaximum ( include , exclude ) ; } string largestNumber ( int arr [ ] , int N , int K ) { vector < vector < string > > dp ( N + 1 , vector < string > ( K + 1 , " - 1" ) ) ; string ans = recursion ( arr , 0 , N , K , dp ) ; return ( ans == " " ? "0" : ans ) ; } int main ( ) { int arr [ ] = { 3 , 12 , 9 , 5 , 3 , 4 , 6 , 5 , 10 } ; int K = 14 ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << largestNumber ( arr , N , K ) ; return 0 ; }