Maximum size of subset such that product of all subset elements is a factor of N | Java program for the above approach ; 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
import java . util . * ; class GFG { static int maximizeSubset ( int N , int [ ] arr , int M , int x ) { if ( x == M ) { return 0 ; } int ans = 0 ; for ( int i = x ; i < M ; i ++ ) { if ( N % arr [ i ] == 0 ) { ans = Math . max ( ans , maximizeSubset ( N / arr [ i ] , arr , M , x + 1 ) + 1 ) ; } } return ans ; } public static void main ( String [ ] args ) { int N = 64 ; int [ ] arr = { 1 , 2 , 4 , 8 , 16 , 32 } ; int M = arr . length ; System . out . println ( maximizeSubset ( N , arr , M , 0 ) ) ; } }