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
function findMedianOfsubSum ( arr , N ) { var sum = 0 ; for ( var i = 0 ; i < N ; i ++ ) { sum += arr [ i ] ; } arr . sort ( ( a , b ) => a - b ) var dp = Array . from ( Array ( N ) , ( ) => Array ( sum + 1 ) . fill ( 0 ) ) ; for ( var i = 0 ; i < N ; i ++ ) { dp [ i ] [ 0 ] = 1 ; } dp [ 0 ] [ arr [ 0 ] ] = 1 ; for ( var i = 1 ; i < N ; i ++ ) { for ( var j = 1 ; j <= sum ; j ++ ) { if ( j >= arr [ i ] ) { dp [ i ] [ j ] = dp [ i - 1 ] [ j ] + dp [ i - 1 ] [ j - arr [ i ] ] ; } else { dp [ i ] [ j ] = dp [ i - 1 ] [ j ] ; } } } var sumSub = [ ] ; for ( var j = 1 ; j <= sum ; j ++ ) { var M = dp [ N - 1 ] [ j ] ; for ( var i = 1 ; i <= M ; i ++ ) { sumSub . push ( j ) ; } } var mid = sumSub [ parseInt ( sumSub . length / 2 ) ] ; return mid ; } var arr = [ 2 , 3 , 3 ] ; var N = arr . length document . write ( findMedianOfsubSum ( arr , N ) ) ;