Minimize sum of incompatibilities of K equal | C ++ program for the above approach ; Function to find the minimum incompatibility sum ; Stores the count of element ; Traverse the array ; If number i not occurs in Map ; Put the element in the Map ; Increment the count of i in the Hash Map ; If count of i in Map is greater than K then return - 1 ; Stores all total state ; Traverse over all the state ; If number of set bit is equal to N / K ; Stores the minimum value at a state ; Call the recursive function ; Recursive function to find the minimum required value ; Base Case ; Stores the minimum value of the current state ; If dp [ state ] [ index ] is already calculated ; return dp [ state ] [ index ] ; Traverse over all the bits ; If count of set bit is N / K ; Store the new state after choosing N / K elements ; Stores the minimum and maximum of current subset ; Stores if the elements have been already selected or not ; Stores if it is possible to select N / K elements ; Traverse over the array ; If not chosen already for another subset ; If already chosen for another subset or current subset ; Mark the good false ; Mark the current number visited ; Mark the current position in mask newstate ; Update the maximum and minimum ; If good is true then Update the res ; Update the current sp state ; Return the res ; Driver code ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int k ; int n ; int goal ; vector < vector < int > > dp ; vector < int > bits ; int minimumIncompatibility ( vector < int > A , int K ) { n = A . size ( ) ; k = K ; goal = n / k ; map < int , int > mp ; for ( int i : A ) { if ( mp . find ( i ) != mp . end ( ) ) { mp [ i ] = 0 ; } mp [ i ] ++ ; if ( mp [ i ] > k ) return -1 ; } int state = ( 1 << n ) - 1 ; for ( int i = 0 ; i <= state ; i ++ ) { if ( __builtin_popcount ( i ) == goal ) bits . push_back ( i ) ; } dp . resize ( 1 << n , vector < int > ( k , -1 ) ) ; return dfs ( A , state , 0 ) ; } int dfs ( vector < int > A , int state , int index ) { if ( index >= k ) { return 0 ; } int res = 1000 ; if ( dp [ state ] [ index ] != -1 ) { return dp [ state ] [ index ] ; } for ( int bit : bits ) { if ( __builtin_popcount ( bit ) == goal ) { int newstate = state ; int mn = 100 , mx = -1 ; vector < bool > visit ( n + 1 , false ) ; bool good = true ; for ( int j = 0 ; j < n ; j ++ ) { if ( ( bit & ( 1 << j ) ) != 0 ) { if ( visit [ A [ j ] ] == true || ( state & ( 1 << j ) ) == 0 ) { good = false ; break ; } visit [ A [ j ] ] = true ; newstate = newstate ^ ( 1 << j ) ; mx = max ( mx , A [ j ] ) ; mn = min ( mn , A [ j ] ) ; } } if ( good ) { res = min ( res , mx - mn + dfs ( A , newstate , index + 1 ) ) ; } } } dp [ state ] [ index ] = res ; return res ; } int main ( ) { vector < int > arr = { 1 , 2 , 1 , 4 } ; int K = 2 ; cout << ( minimumIncompatibility ( arr , K ) ) ; }