Number of subsets with a given AND value | Javascript implementation of the approach ; To store states of DP ; Function to return the required count ; Base case ; If the state has been solved before return the value of the state ; Setting the state as solved ; Recurrence relation ; Driver code
var maxN = 20 ; var maxM = 64 ; var dp1 = Array . from ( Array ( maxN ) , ( ) => Array ( maxM ) ) ; var v1 = Array . from ( Array ( maxN ) , ( ) => Array ( maxM ) ) ; function findCnt ( arr , i , curr , n , m ) { if ( i == n ) { return ( curr == m ) ; } if ( v1 [ i ] [ curr ] ) return dp1 [ i ] [ curr ] ; v1 [ i ] [ curr ] = 1 ; dp1 [ i ] [ curr ] = findCnt ( arr , i + 1 , curr , n , m ) + findCnt ( arr , i + 1 , ( curr & arr [ i ] ) , n , m ) ; return dp1 [ i ] [ curr ] ; } var arr = [ 0 , 0 , 0 ] ; var n = arr . length ; var m = 0 ; document . write ( findCnt ( arr , 0 , ( ( 1 << 6 ) - 1 ) , n , m ) ) ;