Lexicographically largest string possible for a given cost of appending characters | C ++ Program to implement the above approach ; Function to find the lexicographically largest String possible ; If sum is less than 0 ; If sum is equal to 0 ; If sum is less than 0 ; Add current character ; Check if selecting current character generates lexicographically largest String ; Backtrack if solution not found ; Find the lexicographically largest String excluding the current character ; Function to print the lexicographically largest String generated ; Function call ; Stores the String ; Print the lexicographically largest String formed ; Driver code ; Cost of adding each alphabet ; Cost of generating the String
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool lexi_largest_String ( int a [ ] , int i , int sum , vector < int > & v ) { if ( sum < 0 ) return false ; if ( sum == 0 ) return true ; if ( i < 0 ) return false ; v . push_back ( i ) ; if ( lexi_largest_String ( a , i , sum - a [ i ] , v ) ) return true ; auto it = v . end ( ) ; it -- ; v . erase ( it ) ; return lexi_largest_String ( a , i - 1 , sum , v ) ; } void generateString ( int a [ ] , int sum ) { vector < int > v ; lexi_largest_String ( a , 25 , sum , v ) ; string s = " " ; for ( int j = 0 ; j < v . size ( ) ; j ++ ) s += ( char ) ( v [ j ] + ' a ' ) ; cout << s << endl ; } int main ( ) { int a [ ] = { 1 , 1 , 2 , 33 , 4 , 6 , 9 , 7 , 36 , 32 , 58 , 32 , 28 , 904 , 22 , 255 , 47 , 69 , 558 , 544 , 21 , 36 , 48 , 85 , 48 , 58 } ; int sum = 236 ; generateString ( a , sum ) ; return 0 ; }