Count distinct possible Bitwise XOR values of subsets of an array | C ++ program for the above approach ; Stores the Bitwise XOR of every possible subset ; Function to generate all combinations of subsets and store their Bitwise XOR in set S ; If the end of the subset is reached ; Stores the Bitwise XOR of the current subset ; Iterate comb [ ] to find XOR ; Insert the Bitwise XOR of R elements ; Otherwise , iterate to generate all possible subsets ; Recursive call for next index ; Function to find the size of the set having Bitwise XOR of all the subsets of the given array ; Iterate ove the given array ; Generate all possible subsets ; Print the size of the set ; Driver Code ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; unordered_set < int > s ; void countXOR ( int arr [ ] , int comb [ ] , int start , int end , int index , int r ) { if ( index == r ) { int new_xor = 0 ; for ( int j = 0 ; j < r ; j ++ ) { new_xor ^= comb [ j ] ; } s . insert ( new_xor ) ; return ; } for ( int i = start ; i <= end && end - i + 1 >= r - index ; i ++ ) { comb [ index ] = arr [ i ] ; countXOR ( arr , comb , i + 1 , end , index + 1 , r ) ; } } void maxSizeSet ( int arr [ ] , int N ) { for ( int r = 2 ; r <= N ; r ++ ) { int comb [ r + 1 ] ; countXOR ( arr , comb , 0 , N - 1 , 0 , r ) ; } cout << s . size ( ) << endl ; } int main ( ) { int arr [ ] = { 1 , 2 , 3 , 4 , 5 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; maxSizeSet ( arr , N ) ; return 0 ; }