Median of all non | Function to calculate the median of all possible subsets by given operations ; Stores sum of elements of arr [ ] ; Traverse the array arr [ ] ; Update sum ; Sort the array ; DP [ i ] [ j ] : Stores total number of ways to form the sum j by either selecting ith element or not selecting ith item . ; Base case ; Fill dp [ i ] [ 0 ] ; Base case ; Fill all the DP states based on the mentioned DP relation ; If j is greater than or equal to arr [ i ] ; Update dp [ i ] [ j ] ; Update dp [ i ] [ j ] ; Stores all possible subset sum ; Traverse all possible subset sum ; Stores count of subsets whose sum is j ; Itearate over the range [ 1 , M ] ; Insert j into sumSub ; Stores middle element of sumSub ; Driver Code
def findMedianOfsubSum ( arr , N ) : NEW_LINE INDENT sum = 0 NEW_LINE for i in range ( N ) : NEW_LINE INDENT sum += arr [ i ] NEW_LINE DEDENT arr . sort ( reverse = False ) NEW_LINE dp = [ [ 0 for i in range ( sum + 1 ) ] for j in range ( N ) ] NEW_LINE for i in range ( N ) : NEW_LINE INDENT dp [ i ] [ 0 ] = 1 NEW_LINE DEDENT dp [ 0 ] [ arr [ 0 ] ] = 1 NEW_LINE for i in range ( 1 , N , 1 ) : NEW_LINE INDENT for j in range ( 1 , sum + 1 , 1 ) : NEW_LINE INDENT if ( j >= arr [ i ] ) : NEW_LINE INDENT dp [ i ] [ j ] = ( dp [ i - 1 ] [ j ] + dp [ i - 1 ] [ j - arr [ i ] ] ) NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] [ j ] = dp [ i - 1 ] [ j ] NEW_LINE DEDENT DEDENT DEDENT sumSub = [ ] NEW_LINE for j in range ( 1 , sum + 1 , 1 ) : NEW_LINE INDENT M = dp [ N - 1 ] [ j ] NEW_LINE for i in range ( 1 , M + 1 , 1 ) : NEW_LINE INDENT sumSub . append ( j ) NEW_LINE DEDENT DEDENT mid = sumSub [ len ( sumSub ) // 2 ] NEW_LINE return mid NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 2 , 3 , 3 ] NEW_LINE N = len ( arr ) NEW_LINE print ( findMedianOfsubSum ( arr , N ) ) NEW_LINE DEDENT