Smallest subset of maximum sum possible by splitting array into two subsets | Python 3 program for the 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 subseta ; 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
from collections import defaultdict NEW_LINE def findSubset ( arr ) : NEW_LINE INDENT N = len ( arr ) NEW_LINE mp = defaultdict ( int ) NEW_LINE totSum = 0 NEW_LINE s = 0 NEW_LINE flag = 0 NEW_LINE ans = [ ] NEW_LINE for i in range ( len ( arr ) ) : NEW_LINE INDENT totSum += arr [ i ] NEW_LINE mp [ arr [ i ] ] = mp [ arr [ i ] ] + 1 NEW_LINE DEDENT arr . sort ( ) NEW_LINE i = N - 1 NEW_LINE while ( i >= 0 ) : NEW_LINE INDENT frq = mp [ arr [ i ] ] NEW_LINE if ( ( frq + len ( ans ) ) < ( N - ( frq + len ( ans ) ) ) ) : NEW_LINE INDENT for k in range ( frq ) : NEW_LINE INDENT ans . append ( arr [ i ] ) NEW_LINE totSum -= arr [ i ] NEW_LINE s += arr [ i ] NEW_LINE i -= 1 NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT i -= frq NEW_LINE DEDENT if ( s > totSum ) : NEW_LINE INDENT flag = 1 NEW_LINE break NEW_LINE DEDENT DEDENT if ( flag == 1 ) : NEW_LINE INDENT for i in range ( len ( ans ) - 1 , - 1 , - 1 ) : NEW_LINE INDENT print ( ans [ i ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT print ( - 1 ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 5 , 3 , 2 , 4 , 1 , 2 ] NEW_LINE findSubset ( arr ) NEW_LINE DEDENT