Maximum subset sum such that no two elements in set have same digit in them | Python3 implementation of above approach ; Function to create mask for every number ; Recursion for Filling DP array ; Base Condition ; Recurrence Relation ; Function to find Maximum Subset Sum ; Initialize DP array ; Iterate over all possible masks of 10 bit number ; Driver Code
dp = [ 0 ] * 1024 ; NEW_LINE def get_binary ( u ) : NEW_LINE INDENT ans = 0 ; NEW_LINE while ( u ) : NEW_LINE INDENT rem = u % 10 ; NEW_LINE ans |= ( 1 << rem ) ; NEW_LINE u //= 10 ; NEW_LINE DEDENT return ans ; NEW_LINE DEDENT def recur ( u , array , n ) : NEW_LINE INDENT if ( u == 0 ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT if ( dp [ u ] != - 1 ) : NEW_LINE INDENT return dp [ u ] ; NEW_LINE DEDENT temp = 0 ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT mask = get_binary ( array [ i ] ) ; NEW_LINE if ( ( mask u ) == u ) : NEW_LINE INDENT dp [ u ] = max ( max ( 0 , dp [ u ^ mask ] ) + array [ i ] , dp [ u ] ) ; NEW_LINE DEDENT DEDENT return dp [ u ] ; NEW_LINE DEDENT def solve ( array , n ) : NEW_LINE INDENT i = 0 NEW_LINE while ( i < ( 1 << 10 ) ) : NEW_LINE INDENT dp [ i ] = - 1 ; NEW_LINE i += 1 NEW_LINE DEDENT ans = 0 ; NEW_LINE i = 0 NEW_LINE while ( i < ( 1 << 10 ) ) : NEW_LINE INDENT ans = max ( ans , recur ( i , array , n ) ) ; NEW_LINE i += 1 NEW_LINE DEDENT return ans ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT array = [ 22 , 132 , 4 , 45 , 12 , 223 ] ; NEW_LINE n = len ( array ) ; NEW_LINE print ( solve ( array , n ) ) ; NEW_LINE DEDENT