Number of subsets with sum divisible by m | Use Dynamic Programming to find sum of subsequences . ; Find sum pf array elements ; dp [ i ] [ j ] would be > 0 if arr [ 0. . i - 1 ] has a subsequence with sum equal to j . ; There is always sum equals zero ; Fill up the dp table ; Initialize the counter ; Check if the sum exists ; check sum is divisible by m ; Driver Code
function sumSubSequence ( arr , len , m ) { let sum = 0 ; for ( let x = 0 ; x < arr . length ; x ++ ) { sum += arr [ x ] ; } let dp = new Array ( len + 1 ) ; for ( let i = 0 ; i < dp . length ; i ++ ) { dp [ i ] = new Array ( sum + 1 ) ; for ( let j = 0 ; j < dp [ i ] . length ; j ++ ) { dp [ i ] [ j ] = 0 ; } } for ( let i = 0 ; i <= len ; i ++ ) dp [ i ] [ 0 ] ++ ; for ( let i = 1 ; i <= len ; i ++ ) { dp [ i ] [ arr [ i - 1 ] ] ++ ; for ( let j = 1 ; j <= sum ; j ++ ) { if ( dp [ i - 1 ] [ j ] > 0 ) { dp [ i ] [ j ] ++ ; dp [ i ] [ j + arr [ i - 1 ] ] ++ ; } } } let count = 0 ; for ( let j = 1 ; j <= sum ; j ++ ) if ( dp [ len ] [ j ] > 0 ) if ( j % m == 0 ) count += dp [ len ] [ j ] ; return count ; } let arr = [ 1 , 2 , 3 ] ; let m = 3 ; let len = arr . length ; document . write ( sumSubSequence ( arr , len , m ) + " " ) ;