Split array into two equal length subsets such that all repetitions of a number lies in a single subset | Java 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
import java . io . * ; import java . util . * ; class GFG { private static int [ ] findSubsets ( int [ ] arr ) { HashMap < Integer , Integer > M = new HashMap < > ( ) ; for ( int i = 0 ; i < arr . length ; i ++ ) { M . put ( arr [ i ] , M . getOrDefault ( arr [ i ] , 0 ) + 1 ) ; } int [ ] subsets = new int [ M . size ( ) ] ; int i = 0 ; for ( Map . Entry < Integer , Integer > playerEntry : M . entrySet ( ) ) { subsets [ i ++ ] = playerEntry . getValue ( ) ; } return subsets ; } private static boolean subsetSum ( int [ ] subsets , int target ) { boolean [ ] [ ] dp = new boolean [ subsets . length + 1 ] [ target + 1 ] ; for ( int i = 0 ; i < dp . length ; 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 ] ; } public static void divideInto2Subset ( int [ ] arr ) { int [ ] subsets = findSubsets ( arr ) ; if ( ( arr . length ) % 2 == 1 ) { System . out . println ( " No " ) ; return ; } boolean isPossible = subsetSum ( subsets , arr . length / 2 ) ; if ( isPossible ) { System . out . println ( " Yes " ) ; } else { System . out . println ( " No " ) ; } } public static void main ( String [ ] args ) { int [ ] arr = { 2 , 1 , 2 , 3 } ; divideInto2Subset ( arr ) ; } }