Number of subsets with a given AND value | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define maxN  20 NEW_LINE #define maxM  64 NEW_LINE int dp1 [ maxN ] [ maxM ] ; bool v1 [ maxN ] [ maxM ] ; int findCnt ( int * arr , int i , int curr , int n , int 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 ] ; } int main ( ) { int arr [ ] = { 0 , 0 , 0 } ; int n = sizeof ( arr ) / sizeof ( int ) ; int m = 0 ; cout << findCnt ( arr , 0 , ( ( 1 << 6 ) - 1 ) , n , m ) ; return 0 ; }