Construct the largest number whose sum of cost of digits is K | Java 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
import java . util . * ; public class Main { 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 , Vector < Vector < String > > dp ) { if ( K == 0 ) { return " " ; } if ( K < 0 idx == N ) { return "0" ; } if ( dp . get ( idx ) . get ( K ) != " - 1" ) return dp . get ( idx ) . get ( K ) ; String include = String . valueOf ( idx + 1 ) + recursion ( arr , 0 , N , K - arr [ idx ] , dp ) ; String exclude = recursion ( arr , idx + 1 , N , K , dp ) ; dp . get ( idx ) . set ( K , getMaximum ( include , exclude ) ) ; return dp . get ( idx ) . get ( K ) ; } static String largestNumber ( int [ ] arr , int N , int K ) { Vector < Vector < String > > dp = new Vector < Vector < String > > ( ) ; for ( int i = 0 ; i < N + 1 ; i ++ ) { dp . add ( new Vector < String > ( ) ) ; for ( int j = 0 ; j < K + 1 ; j ++ ) { dp . get ( i ) . add ( " - 1" ) ; } } String ans = recursion ( arr , 0 , N , K , dp ) ; return ans == " " ? "0" : ans ; } public static void main ( String [ ] args ) { int [ ] arr = { 3 , 12 , 9 , 5 , 3 , 4 , 6 , 5 , 10 } ; int K = 14 ; int N = arr . length ; System . out . print ( largestNumber ( arr , N , K ) ) ; } }