Maximum sum of Bitwise XOR of all elements of two equal length subsets | C ++ program for the above approach ; Function that finds the maximum Bitwise XOR sum of the two subset ; Check if the current state is already computed ; Initialize answer to minimum value ; Iterate through all possible pairs ; Check whether ith bit and jth bit of mask is not set then pick the pair ; For all possible pairs find maximum value pick current a [ i ] , a [ j ] and set i , j th bits in mask ; Store the maximum value and return the answer ; Driver Code ; Given array arr [ ] ; Declare Initialize the dp states ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int xorSum ( int a [ ] , int n , int mask , int dp [ ] ) { if ( dp [ mask ] != -1 ) { return dp [ mask ] ; } int max_value = 0 ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = i + 1 ; j < n ; j ++ ) { if ( i != j && ( mask & ( 1 << i ) ) == 0 && ( mask & ( 1 << j ) ) == 0 ) { max_value = max ( max_value , ( a [ i ] ^ a [ j ] ) + xorSum ( a , n , ( mask | ( 1 << i ) | ( 1 << j ) ) , dp ) ) ; } } } return dp [ mask ] = max_value ; } int main ( ) { int n = 4 ; int arr [ ] = { 1 , 2 , 3 , 4 } ; int dp [ ( 1 << n ) + 5 ] ; memset ( dp , -1 , sizeof ( dp ) ) ; cout << ( xorSum ( arr , n , 0 , dp ) ) ; }