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
using System ; using System . Collections . Generic ; class GFG { static int [ ] findSubsets ( int [ ] arr ) { Dictionary < int , int > M = new Dictionary < int , int > ( ) ; for ( int i = 0 ; i < arr . Length ; i ++ ) { if ( M . ContainsKey ( arr [ i ] ) ) { M [ arr [ i ] ] ++ ; } else { M [ arr [ i ] ] = 1 ; } } int [ ] subsets = new int [ M . Count ] ; int I = 0 ; foreach ( KeyValuePair < int , int > playerEntry in M ) { subsets [ I ] = playerEntry . Value ; I ++ ; } return subsets ; } static bool subsetSum ( int [ ] subsets , int target ) { bool [ , ] dp = new bool [ subsets . Length + 1 , target + 1 ] ; for ( int i = 0 ; i < dp . GetLength ( 0 ) ; i ++ ) dp [ i , 0 ] = true ; for ( int i = 1 ; i <= subsets . Length ; 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 [ subsets . Length , target ] ; } static void divideInto2Subset ( int [ ] arr ) { int [ ] subsets = findSubsets ( arr ) ; if ( ( arr . Length ) % 2 == 1 ) { Console . WriteLine ( " No " ) ; return ; } bool isPossible = subsetSum ( subsets , arr . Length / 2 ) ; if ( isPossible ) { Console . WriteLine ( " Yes " ) ; } else { Console . WriteLine ( " No " ) ; } } static void Main ( ) { int [ ] arr = { 2 , 1 , 2 , 3 } ; divideInto2Subset ( arr ) ; } }