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
using System ; using System . Collections . Generic ; class GFG { static string getMaximum ( string S , string T ) { if ( S . IndexOf ( "0" ) > - 1 ) return T ; if ( T . IndexOf ( "0" ) > - 1 ) return S ; return ( S . Length > T . Length ? S : T ) ; } static string recursion ( int [ ] arr , int idx , int N , int K , List < List < string > > dp ) { if ( K == 0 ) { return " " ; } if ( K < 0 idx == N ) { return "0" ; } if ( dp [ idx ] [ K ] != " - 1" ) return dp [ idx ] [ K ] ; string include = ( idx + 1 ) . ToString ( ) + recursion ( arr , 0 , N , K - arr [ idx ] , dp ) ; string exclude = recursion ( arr , idx + 1 , N , K , dp ) ; return dp [ idx ] [ K ] = getMaximum ( include , exclude ) ; } static string largestNumber ( int [ ] arr , int N , int K ) { List < List < string > > dp = new List < List < string > > ( ) ; for ( int i = 0 ; i < N + 1 ; i ++ ) { dp . Add ( new List < string > ( ) ) ; for ( int j = 0 ; j < K + 1 ; j ++ ) { dp [ i ] . Add ( " - 1" ) ; } } string ans = recursion ( arr , 0 , N , K , dp ) ; return ( ans == " " ? "0" : ans ) ; } static void Main ( ) { int [ ] arr = { 3 , 12 , 9 , 5 , 3 , 4 , 6 , 5 , 10 } ; int K = 14 ; int N = arr . Length ; Console . Write ( largestNumber ( arr , N , K ) ) ; } }