4 Numbers with highest Xor

Refrence : https://www.interviewbit.com/test/f182f1d31b/?signature=BAhpA5Y9DA%3D%3D--f8f7b518aa09db01aca7d19195ffaebbb6b911a4#/problem_2


--------------------------------------------------------------------------------------------------------------------------------------------

int ans = -1;
void get_All_subsequences_with_len_four(vector<int>& A , int idx , int curr_xor , int len){
    if(len == 4){
        // possible candidate answer
        ans = max(ans , curr_xor );
        return;
    }
    
    if(idx == A.size())return ;
    
   get_All_subsequences_with_len_four(A , idx + 1 , curr_xor , len);// current idx element do not come in subsequence
   get_All_subsequences_with_len_four(A , idx + 1 , curr_xor ^ A[idx] , len + 1); // current idx element come in  subsequence
}
int Solution::solve(vector<int> &A) {
   // similar to - Getting all subsequences 
   // Idea : Each element has two options either it will come in subsequence or not come in subsequence.
   // we will explore all the subsequences of size 4 in our array and return the maximum xor value
   // A.size() is atmax 50 
   // To choose subsequnce of 4 from the array , total combinations are 50C4 ~ 230300 
   // therefore. bruteforce work here
   
// ----------- Using for loops -----------------
//   int max_xor = 0 ;
//   for(int i=0 ;i<A.size() ;i++){
//       for(int j=i+1; j<A.size() ; j++){
//           for(int k=j+1; k <A.size() ; k++){
//               for(int l=k+1 ; l < A.size() ; l++){
//                   int cur_xor = A[i]^A[j]^A[k]^A[l];
//                   max_xor = max(max_xor , cur_xor);
//               }
//           }
//       }
//   }
//   return max_xor;

//------------ Backtracking ----------------
int idx = 0 , current_xor = 0 , len = 0 ;
ans = 0;
get_All_subsequences_with_len_four(A , idx , current_xor , len);
return ans;

   
   
    
}