Count no . of ordered subsets having a particular XOR value | 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 Code
< ? php function subsetXOR ( $ arr , $ n , $ K ) { $ max_ele = $ arr [ 0 ] ; for ( $ i = 1 ; $ i < $ n ; $ i ++ ) if ( $ arr [ $ i ] > $ max_ele ) $ max_ele = $ arr [ $ i ] ; $ m = ( 1 << ( floor ( log ( $ max_ele , 2 ) ) + 1 ) ) - 1 ; $ dp = array ( array ( array ( ) ) ) ; for ( $ i = 0 ; $ i <= $ n ; $ i ++ ) for ( $ j = 0 ; $ j <= $ m ; $ j ++ ) for ( $ k = 0 ; $ k <= $ n ; $ k ++ ) $ dp [ $ i ] [ $ j ] [ $ k ] = 0 ; for ( $ i = 0 ; $ i <= $ n ; $ i ++ ) $ dp [ $ i ] [ 0 ] [ 0 ] = 1 ; for ( $ i = 1 ; $ i <= $ n ; $ i ++ ) { for ( $ j = 0 ; $ j <= $ m ; $ j ++ ) { for ( $ 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 ] ; } } } } $ ans = 0 ; for ( $ i = 1 ; $ i <= $ n ; $ i ++ ) { $ ans += $ dp [ $ n ] [ $ K ] [ $ i ] ; } return $ ans ; } $ arr = [ 1 , 2 , 3 ] ; $ k = 1 ; $ n = sizeof ( $ arr ) ; echo subsetXOR ( $ arr , $ n , $ k ) ; ? >