Number of subsets with sum divisible by M | Set 2 | Javascript implementation of the approach ; To store the states of DP ; Function to find 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 = 10 var dp = Array . from ( Array ( maxN ) , ( ) => Array ( maxM ) ) ; var v = Array . from ( Array ( maxN ) , ( ) => Array ( maxM ) ) ; function findCnt ( arr , i , curr , n , m ) { if ( i == n ) { if ( curr == 0 ) return 1 ; else return 0 ; } if ( v [ i ] [ curr ] ) return dp [ i ] [ curr ] ; v [ i ] [ curr ] = 1 ; dp [ i ] [ curr ] = findCnt ( arr , i + 1 , curr , n , m ) + findCnt ( arr , i + 1 , ( curr + arr [ i ] ) % m , n , m ) ; return dp [ i ] [ curr ] ; } var arr = [ 3 , 3 , 3 , 3 ] ; var n = arr . length ; var m = 6 ; document . write ( findCnt ( arr , 0 , 0 , n , m ) - 1 ) ;