Number of subsets with a given OR value | Java 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
import java . util . * ; class GFG { static int maxN = 20 ; static int maxM = 64 ; static int [ ] [ ] dp = new int [ maxN ] [ maxM ] ; static boolean [ ] [ ] v = new boolean [ maxN ] [ maxM ] ; static int findCnt ( int [ ] arr , int i , int curr , int n , int m ) { if ( i == n ) { return ( curr == m ? 1 : 0 ) ; } if ( v [ i ] [ curr ] ) return dp [ i ] [ curr ] ; v [ i ] [ curr ] = true ; dp [ i ] [ curr ] = findCnt ( arr , i + 1 , curr , n , m ) + findCnt ( arr , i + 1 , ( curr arr [ i ] ) , n , m ) ; return dp [ i ] [ curr ] ; } public static void main ( String [ ] args ) { int arr [ ] = { 2 , 3 , 2 } ; int n = arr . length ; int m = 3 ; System . out . println ( findCnt ( arr , 0 , 0 , n , m ) ) ; } }