Maximum size of subset such that product of all subset elements is a factor of N | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maximizeSubset ( int N , int arr [ ] , int M , int x = 0 ) { if ( x == M ) { return 0 ; } int ans = 0 ; for ( int i = x ; i < M ; i ++ ) { if ( N % arr [ i ] == 0 ) { ans = max ( ans , maximizeSubset ( N / arr [ i ] , arr , M , x + 1 ) + 1 ) ; } } return ans ; } int main ( ) { int N = 64 ; int arr [ ] = { 1 , 2 , 4 , 8 , 16 , 32 } ; int M = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << maximizeSubset ( N , arr , M ) ; return 0 ; }