Smallest subset of maximum sum possible by splitting array into two subsets | Java program for above approach ; Function to split array elements into two subsets having sum of the smaller subset maximized ; Stores the size of the array ; Stores the frequency of array elements ; Stores the total sum of the array ; Stores the sum of the resultant set ; Stores if it is possible to split the array that satisfies the conditions ; Stores the elements of the first subset ; Traverse the array arr [ ] ; Increment total sum ; Increment count of arr [ i ] ; Sort the array arr [ ] ; Stores the index of the last element of the array ; Traverse the array arr [ ] ; Stores the frequency of arr [ i ] ; If frq + ans . size ( ) is at most remaining size ; Append arr [ i ] to ans ; Decrement totSum by arr [ i ] ; Increment s by arr [ i ] ; Otherwise , decrement i by frq ; If s is greater than totSum ; Mark flag 1 ; If flag is equal to 1 ; Print the arrList ans ; Otherwise , print " - 1" ; Driver Code
import java . io . * ; import java . lang . * ; import java . util . * ; class GFG { static void findSubset ( int [ ] arr ) { int N = arr . length ; Map < Integer , Integer > map = new HashMap < > ( ) ; int totSum = 0 ; int s = 0 ; int flag = 0 ; ArrayList < Integer > ans = new ArrayList < > ( ) ; for ( int i = 0 ; i < arr . length ; i ++ ) { totSum += arr [ i ] ; map . put ( arr [ i ] , map . getOrDefault ( arr [ i ] , 0 ) + 1 ) ; } Arrays . sort ( arr ) ; int i = N - 1 ; while ( i >= 0 ) { int frq = map . get ( arr [ i ] ) ; if ( ( frq + ans . size ( ) ) < ( N - ( frq + ans . size ( ) ) ) ) { for ( int k = 0 ; k < frq ; k ++ ) { ans . add ( arr [ i ] ) ; totSum -= arr [ i ] ; s += arr [ i ] ; i -- ; } } else { i -= frq ; } if ( s > totSum ) { flag = 1 ; break ; } } if ( flag == 1 ) { for ( i = ans . size ( ) - 1 ; i >= 0 ; i -- ) { System . out . print ( ans . get ( i ) + " ▁ " ) ; } } else { System . out . print ( - 1 ) ; } } public static void main ( String [ ] args ) { int [ ] arr = { 5 , 3 , 2 , 4 , 1 , 2 } ; findSubset ( arr ) ; } }