Maximum size of subset such that product of all subset elements is a factor of N | Function to find the maximum size of the subset such that the product of subset elements is a factor of N ; Base Case ; Stores maximum size of valid subset ; Traverse the given array ; If N % arr [ i ] = 0 , include arr [ i ] in a subset and recursively call for the remaining array integers ; Return Answer ; Driver Code
def maximizeSubset ( N , arr , M , x = 0 ) : NEW_LINE INDENT if ( x == M ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT ans = 0 NEW_LINE for i in range ( x , M ) : NEW_LINE INDENT if ( N % arr [ i ] == 0 ) : NEW_LINE INDENT ans = max ( ans , maximizeSubset ( N // arr [ i ] , arr , M , x + 1 ) + 1 ) NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT N = 64 NEW_LINE arr = [ 1 , 2 , 4 , 8 , 16 , 32 ] NEW_LINE M = len ( arr ) NEW_LINE print ( maximizeSubset ( N , arr , M ) ) NEW_LINE