Median of all non | Java program to implement the above approach ; 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 . ; Initialize all the DP states ; 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
import java . util . * ; class GFG { static int findMedianOfsubSum ( int arr [ ] , int N ) { int sum = 0 ; for ( int i = 0 ; i < N ; i ++ ) { sum += arr [ i ] ; } Arrays . sort ( arr ) ; int [ ] [ ] dp = new int [ N ] [ sum + 1 ] ; for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < sum + 1 ; j ++ ) dp [ i ] [ j ] = 0 ; } for ( int i = 0 ; i < N ; i ++ ) { dp [ i ] [ 0 ] = 1 ; } dp [ 0 ] [ arr [ 0 ] ] = 1 ; for ( int i = 1 ; i < N ; i ++ ) { for ( int 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 ] ; } } } Vector < Integer > sumSub = new Vector < Integer > ( ) ; for ( int j = 1 ; j <= sum ; j ++ ) { int M = dp [ N - 1 ] [ j ] ; for ( int i = 1 ; i <= M ; i ++ ) { sumSub . add ( j ) ; } } int mid = sumSub . get ( sumSub . size ( ) / 2 ) ; return mid ; } public static void main ( String args [ ] ) { int arr [ ] = { 2 , 3 , 3 } ; int N = arr . length ; System . out . print ( findMedianOfsubSum ( arr , N ) ) ; } }