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
def modularSum ( arr , n , m ) : NEW_LINE INDENT if ( n > m ) : NEW_LINE INDENT return True NEW_LINE DEDENT DP = [ False for i in range ( m ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( DP [ 0 ] ) : NEW_LINE INDENT return True NEW_LINE DEDENT temp = [ False for i in range ( m ) ] NEW_LINE for j in range ( m ) : NEW_LINE INDENT if ( DP [ j ] == True ) : NEW_LINE INDENT if ( DP [ ( j + arr [ i ] ) % m ] == False ) : NEW_LINE INDENT temp [ ( j + arr [ i ] ) % m ] = True NEW_LINE DEDENT DEDENT DEDENT for j in range ( m ) : NEW_LINE INDENT if ( temp [ j ] ) : NEW_LINE INDENT DP [ j ] = True NEW_LINE DEDENT DEDENT DP [ arr [ i ] % m ] = True NEW_LINE DEDENT return DP [ 0 ] NEW_LINE DEDENT arr = [ 1 , 7 ] NEW_LINE n = len ( arr ) NEW_LINE m = 5 NEW_LINE print ( " YES " ) if ( modularSum ( arr , n , m ) ) else print ( " NO " ) NEW_LINE