decreasing runtime:paying up

import java.io.BufferedReader;
import java.io.InputStreamReader;

 class test1 {
    public static void main(String[] args)throws Exception {
     
       
        
         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
         
         int lin = Integer.parseInt(br.readLine());
         String str[];
         
          while(lin-->0)
         {
             str = br.readLine().split(" ");
             int n = Integer.parseInt(str[0]);
             int m = Integer.parseInt(str[1]);
             int flag=0;
                          int a[] = new int[n] ;

             for(int k =0;k<n;k++)
             {
                 
                 a[k]=Integer.parseInt(br.readLine());
             }
             
             
             for(int i =1;i<Math.pow(2,n);i++)
             {
                 int sum =0;
                 
for(int j=0; j<n; j++)
{

   if (( i & (1<<j) )>0) //testing if the jth bit of i is set
   {

      sum+=a[j];
   }
   if(sum==m)
             {
                 System.out.println("Yes");
                 flag=1;
                 break;
             } 
                 
}            if(flag==1)
             {
                
                 break;
             }     
                 
               }
             
             
             if(flag==0)
             {
               System.out.println("No");  
             }
             
            
             
             
             
             
         }
    }
}

getting a time around 9.7 in codechef is there anyway i can decrease it…!

Java is slow compartvly. Same in c/c++ wil need much less time

you can have a look at my solution…i have used the sum of subsets concept…LINK!!!

it had a time of 1.27 secs in JAVA…i hope this will help…pls do feel free to ask ne part of the algo which u may fail to understand…:slight_smile:

EDIT 1

this is your corrected & AC code…LINK!!!

EDIT 2

else if does not work…as you need to consider the case when the “current pos is not selected” as one of the cases…so we need to use if!!!

and flag is used so that the code knows that we have come to the required sum…and there is no need to check the further cases…and also if all the cases are checked and no such sum is found then we can print “No”…hope u get it…:slight_smile:

1 Like

hii @kunal361
i used backtracking but its giving the wrong answer in codechef :frowning:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;





 class test2 {
      static int arr[];
    
     static int dvalue;
    
     public static void  subsetsum(int index,int cursum,int remsum)
     {
    
         if (arr[index]+cursum==dvalue)
         {
    
             System.out.println("Yes");
         }
         else if(index+1<arr.length && cursum+arr[index]+arr[index+1]<=dvalue)
         {
    
             subsetsum(index+1,cursum+arr[index],remsum-arr[index]);
             
         }
         else if(index+1<arr.length && cursum+arr[index+1]<=dvalue && cursum+remsum-arr[index]>=dvalue)
                 {
    
                     subsetsum(index+1,cursum,remsum-arr[index]);
                 }
         
         else 
                 {
                     System.out.println("No");
                 }
     }
     
     
    public static void main(String[] args)throws Exception {
     
       
        
         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
         
         int lin = Integer.parseInt(br.readLine());
         String str[];
         
          while(lin-->0)
         {
             int totalsum=0;
             str = br.readLine().split(" ");
             int n = Integer.parseInt(str[0]);
             int m = Integer.parseInt(str[1]);
             
                          int a[] = new int[n] ;

             for(int k =0;k<n;k++)
             {
                 
                 a[k]=Integer.parseInt(br.readLine());
             }
             
             Arrays.sort(a);
    
             arr=a;
    
             dvalue=m;
            for(int k =0;k<n;k++)
             {
                 
                totalsum+=a[k];
             }
             
             subsetsum(0,0,totalsum);
             
             
             
             
            
            
             
             
             
             
         }
    }
}

but its running fine in my netbeans !

@kunal361
did the same but am getting wrong answer …!

@kunal361 thnx a lot got it can u pls explain why else if was not working correctly in my pervious code and flag has to b used for it.