Number of subsets with sum 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
def sumSubSequence ( arr , length , m ) : NEW_LINE INDENT summ = 0 NEW_LINE for i in arr : NEW_LINE INDENT summ += i NEW_LINE DEDENT dp = [ [ 0 for i in range ( summ + 1 ) ] for j in range ( length + 1 ) ] NEW_LINE for i in range ( length + 1 ) : NEW_LINE INDENT dp [ i ] [ 0 ] += 1 NEW_LINE DEDENT for i in range ( 1 , length + 1 ) : NEW_LINE INDENT dp [ i ] [ arr [ i - 1 ] ] += 1 NEW_LINE for j in range ( 1 , summ + 1 ) : NEW_LINE INDENT if dp [ i - 1 ] [ j ] > 0 : NEW_LINE INDENT dp [ i ] [ j ] += 1 NEW_LINE dp [ i ] [ j + arr [ i - 1 ] ] += 1 NEW_LINE DEDENT DEDENT DEDENT count = 0 NEW_LINE for i in range ( 1 , summ + 1 ) : NEW_LINE INDENT if dp [ length ] [ i ] > 0 : NEW_LINE INDENT if i % m == 0 : NEW_LINE INDENT count += dp [ length ] [ i ] NEW_LINE DEDENT DEDENT DEDENT return count NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 1 , 2 , 3 ] NEW_LINE m = 3 NEW_LINE length = len ( arr ) NEW_LINE print ( sumSubSequence ( arr , length , m ) ) NEW_LINE DEDENT