Number of subsets with sum divisible by m | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int sumSubSequence ( vector < int > arr , int len , int m ) { int sum = 0 ; for ( auto x : arr ) sum += x ; vector < vector < int > > dp ( len + 1 , vector < int > ( sum + 1 , 0 ) ) ; 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 ; } int main ( ) { vector < int > arr { 1 , 2 , 3 } ; int m = 3 ; int len = arr . size ( ) ; cout << sumSubSequence ( arr , len , m ) << endl ; return 0 ; }