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
< ? php function modularSum ( $ arr , $ n , $ m ) { if ( $ n > $ m ) return true ; $ DP = Array_fill ( 0 , $ m , false ) ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) { if ( $ DP [ 0 ] ) return true ; $ temp = array_fill ( 0 , $ m , false ) ; for ( $ j = 0 ; $ j < $ m ; $ j ++ ) { if ( $ DP [ $ j ] == true ) { if ( $ DP [ ( $ j + $ arr [ $ i ] ) % $ m ] == false ) $ temp [ ( $ j + $ arr [ $ i ] ) % $ m ] = true ; } } for ( $ j = 0 ; $ j < $ m ; $ j ++ ) if ( $ temp [ $ j ] ) $ DP [ $ j ] = true ; $ DP [ $ arr [ $ i ] % $ m ] = true ; } return $ DP [ 0 ] ; } $ arr = array ( 1 , 7 ) ; $ n = sizeof ( $ arr ) ; $ m = 5 ; if ( modularSum ( $ arr , $ n , $ m ) == true ) echo " YES STRNEWLINE " ; else echo " NO STRNEWLINE " ; ? >