Subset with sum divisible by m | C ++ program to check if there is a subset with sum divisible by m . ; Returns true if there is a subset of arr [ ] with sum divisible by m ; This array will keep track of all the possible sum ( after modulo m ) which can be made using subsets of arr [ ] initialising boolean array with all false ; we 'll loop through all the elements of arr[] ; anytime we encounter a sum divisible by m , we are done ; To store all the new encountered sum ( after modulo ) . It is used to make sure that arr [ i ] is added only to those entries for which DP [ j ] was true before current iteration . ; For each element of arr [ ] , we loop through all elements of DP table from 1 to m and we add current element i . e . , arr [ i ] to all those elements which are true in DP table ; if an element is true in DP table ; We update it in temp and update to DP once loop of j is over ; Updating all the elements of temp to DP table since iteration over j is over ; Also since arr [ i ] is a single element subset , arr [ i ] % m is one of the possible sum ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool modularSum ( int arr [ ] , int n , int m ) { if ( n > m ) return true ; bool DP [ m ] ; memset ( DP , false , m ) ; for ( int i = 0 ; i < n ; i ++ ) { if ( DP [ 0 ] ) return true ; bool temp [ m ] ; memset ( temp , false , m ) ; for ( int j = 0 ; j < m ; j ++ ) { if ( DP [ j ] == true ) { if ( DP [ ( j + arr [ i ] ) % m ] == false ) temp [ ( j + arr [ i ] ) % m ] = true ; } } for ( int j = 0 ; j < m ; j ++ ) if ( temp [ j ] ) DP [ j ] = true ; DP [ arr [ i ] % m ] = true ; } return DP [ 0 ] ; } int main ( ) { int arr [ ] = { 1 , 7 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int m = 5 ; modularSum ( arr , n , m ) ? cout << " YES STRNEWLINE " : cout << " NO STRNEWLINE " ; return 0 ; }