Your task is to create a string S consisting of lowercase English alphabets.You are given an array A of size 26 where
A[i] denotes the cost of using the ith alphabet.

Find the lexicographically largest string S that can be created such that the cost of building the string is exactly
is exactly W.

Input:-
cost[]={252,888,578,746,295,884,198,665,503,868,942,506,718,498,727,338,43,768,783,312,369,712,230,106,102,554};
W=6674;

Output:-zzzzzzzzzzzyyyyqqqq

My solution:- Backtracking + Slightly Improvement in eliminating redundant calls.

public class Cost{

public static void main(String args[]){

 int cost[]={252,888,578,746,295,884,198,665,503,868,942,506,718,498,727,338,43,768,783,312,369,712,230,106,102,554};
 int W=6674;
 boolean flag[]={false};
 
 rec(25,W,cost,"",0,flag);

}

public static void rec(int index,int W,int cost[],String string,int summ,boolean []flag){

    if(flag[0]==false){
      
    if(summ==W){
        System.out.println(string);
        flag[0]=true;
        return;
    }

    for(int i=index;i>=0;i--){
       String p=string;
       int csum=summ;   
       
       if(csum+cost[i]<=W){
           csum +=cost[i];
           p +=(char)(97+i);
           rec(index,W,cost,p,csum,flag); 
       }



    }

    }

}

}

If there is any optimized solution to the problem kindly post the solution or explain the algorithm.Thanks Have a good day.