Number of subsets with sum divisible by M | Set 2 | Python3 implementation of the approach ; To store the states of DP ; Function to find the required count ; Base case ; If the state has been solved before return the value of the state ; Setting the state as solved ; Recurrence relation ; Driver code
maxN = 20 NEW_LINE maxM = 10 NEW_LINE dp = [ [ 0 for i in range ( maxN ) ] for i in range ( maxM ) ] NEW_LINE v = [ [ 0 for i in range ( maxN ) ] for i in range ( maxM ) ] NEW_LINE def findCnt ( arr , i , curr , n , m ) : NEW_LINE INDENT if ( i == n ) : NEW_LINE INDENT if ( curr == 0 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT else : NEW_LINE INDENT return 0 NEW_LINE DEDENT DEDENT if ( v [ i ] [ curr ] ) : NEW_LINE INDENT return dp [ i ] [ curr ] NEW_LINE DEDENT v [ i ] [ curr ] = 1 NEW_LINE dp [ i ] [ curr ] = findCnt ( arr , i + 1 , curr , n , m ) + findCnt ( arr , i + 1 , ( curr + arr [ i ] ) % m , n , m ) NEW_LINE return dp [ i ] [ curr ] NEW_LINE DEDENT arr = [ 3 , 3 , 3 , 3 ] NEW_LINE n = len ( arr ) NEW_LINE m = 6 NEW_LINE print ( findCnt ( arr , 0 , 0 , n , m ) - 1 ) NEW_LINE