Count no . of ordered subsets having a particular XOR value | C ++ implementation of the approach ; Returns count of ordered subsets of arr [ ] with XOR value = K ; Find maximum element in arr [ ] ; Maximum possible XOR value ; The value of dp [ i ] [ j ] [ k ] is the number of subsets of length k having XOR of their elements as j from the set arr [ 0. . . i - 1 ] ; Initializing all the values of dp [ i ] [ j ] [ k ] as 0 ; The xor of empty subset is 0 ; Fill the dp table ; The answer is the number of subsets of all lengths from set arr [ 0. . n - 1 ] having XOR of elements as k ; Driver program to test above function
#include <bits/stdc++.h> NEW_LINE using namespace std ; int subsetXOR ( int arr [ ] , int n , int K ) { int max_ele = arr [ 0 ] ; for ( int i = 1 ; i < n ; i ++ ) if ( arr [ i ] > max_ele ) max_ele = arr [ i ] ; int m = ( 1 << ( int ) ( log2 ( max_ele ) + 1 ) ) - 1 ; int dp [ n + 1 ] [ m + 1 ] [ n + 1 ] ; for ( int i = 0 ; i <= n ; i ++ ) for ( int j = 0 ; j <= m ; j ++ ) for ( int k = 0 ; k <= n ; k ++ ) dp [ i ] [ j ] [ k ] = 0 ; for ( int i = 0 ; i <= n ; i ++ ) dp [ i ] [ 0 ] [ 0 ] = 1 ; for ( int i = 1 ; i <= n ; i ++ ) { for ( int j = 0 ; j <= m ; j ++ ) { for ( int k = 0 ; k <= n ; k ++ ) { dp [ i ] [ j ] [ k ] = dp [ i - 1 ] [ j ] [ k ] ; if ( k != 0 ) { dp [ i ] [ j ] [ k ] += k * dp [ i - 1 ] [ j ^ arr [ i - 1 ] ] [ k - 1 ] ; } } } } int ans = 0 ; for ( int i = 1 ; i <= n ; i ++ ) { ans += dp [ n ] [ K ] [ i ] ; } return ans ; } int main ( ) { int arr [ ] = { 1 , 2 , 3 } ; int k = 1 ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << subsetXOR ( arr , n , k ) ; return 0 ; }