Split array into two equal length subsets such that all repetitions of a number lies in a single subset | C ++ program for the above approach ; Function to create the frequency array of the given array arr [ ] ; Hashmap to store the frequencies ; Store freq for each element ; Get the total frequencies ; Store frequencies in subset [ ] array ; Return frequency array ; Function to check is sum N / 2 can be formed using some subset ; dp [ i ] [ j ] store the answer to form sum j using 1 st i elements ; Initialize dp [ ] [ ] with true ; Fill the subset table in the bottom up manner ; If current element is less than j ; Update current state ; Return the result ; Function to check if the given array can be split into required sets ; Store frequencies of arr [ ] ; If size of arr [ ] is odd then print " Yes " ; Check if answer is true or not ; Print the result ; Driver Code ; Given array arr [ ] ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < int > findSubsets ( vector < int > arr , int N ) { map < int , int > M ; for ( int i = 0 ; i < N ; i ++ ) { M [ arr [ i ] ] ++ ; } vector < int > subsets ; int I = 0 ; for ( auto playerEntry = M . begin ( ) ; playerEntry != M . end ( ) ; playerEntry ++ ) { subsets . push_back ( playerEntry -> second ) ; I ++ ; } return subsets ; } bool subsetSum ( vector < int > subsets , int N , int target ) { bool dp [ N + 1 ] [ target + 1 ] ; for ( int i = 0 ; i < N + 1 ; i ++ ) dp [ i ] [ 0 ] = true ; for ( int i = 1 ; i <= N ; i ++ ) { for ( int j = 1 ; j <= target ; j ++ ) { dp [ i ] [ j ] = dp [ i - 1 ] [ j ] ; if ( j >= subsets [ i - 1 ] ) { dp [ i ] [ j ] |= dp [ i - 1 ] [ j - subsets [ i - 1 ] ] ; } } } return dp [ N ] [ target ] ; } void divideInto2Subset ( vector < int > arr , int N ) { vector < int > subsets = findSubsets ( arr , N ) ; if ( ( N ) % 2 == 1 ) { cout << " No " << endl ; return ; } int subsets_size = subsets . size ( ) ; bool isPossible = subsetSum ( subsets , subsets_size , N / 2 ) ; if ( isPossible ) { cout << " Yes " << endl ; } else { cout << " No " << endl ; } } int main ( ) { vector < int > arr { 2 , 1 , 2 , 3 } ; int N = arr . size ( ) ; divideInto2Subset ( arr , N ) ; return 0 ; }