Number of subsets with sum divisible by m | Java program which returns the Number of sub sequences ( or subsets ) which are 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
class GFG { static int sumSubSequence ( int [ ] arr , int len , int m ) { int sum = 0 ; for ( int x : arr ) { sum += x ; } int [ ] [ ] dp = new int [ len + 1 ] [ sum + 1 ] ; for ( int i = 0 ; i <= len ; i ++ ) dp [ i ] [ 0 ] ++ ; for ( int i = 1 ; i <= len ; i ++ ) { dp [ i ] [ arr [ i - 1 ] ] ++ ; for ( int j = 1 ; j <= sum ; j ++ ) { if ( dp [ i - 1 ] [ j ] > 0 ) { dp [ i ] [ j ] ++ ; dp [ i ] [ j + arr [ i - 1 ] ] ++ ; } } } int count = 0 ; for ( int j = 1 ; j <= sum ; j ++ ) if ( dp [ len ] [ j ] > 0 ) if ( j % m == 0 ) count += dp [ len ] [ j ] ; return count ; } public static void main ( String [ ] args ) { int [ ] arr = { 1 , 2 , 3 } ; int m = 3 ; int len = arr . length ; System . out . print ( sumSubSequence ( arr , len , m ) + "NEW_LINE"); } }