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
function modularSum ( arr , n , m ) { if ( n > m ) return true ; let DP = new Array ( m ) ; for ( let l = 0 ; l < m ; l ++ ) DP [ l ] = false ; for ( let i = 0 ; i < n ; i ++ ) { if ( DP [ 0 ] ) return true ; let temp = new Array ( m ) ; for ( let l = 0 ; l < m ; l ++ ) temp [ l ] = false ; for ( let j = 0 ; j < m ; j ++ ) { if ( DP [ j ] == true ) { if ( DP [ ( j + arr [ i ] ) % m ] == false ) temp [ ( j + arr [ i ] ) % m ] = true ; } } for ( let j = 0 ; j < m ; j ++ ) if ( temp [ j ] ) DP [ j ] = true ; DP [ arr [ i ] % m ] = true ; } return DP [ 0 ] ; } let arr = [ 1 , 7 ] ; let n = arr . length ; let m = 5 ; if ( modularSum ( arr , n , m ) ) document . write ( " " + " " ) ; else document . write ( " " + " " ) ;