Smallest subset with sum greater than all other elements | function to find minimum elements needed . ; calculating HALF of array sum ; sort the array in descending order . ; current sum greater than sum ; Driver Code
< ? php function minElements ( $ arr , $ n ) { $ halfSum = 0 ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) $ halfSum = $ halfSum + $ arr [ $ i ] ; $ halfSum = $ halfSum / 2 ; rsort ( $ arr ) ; $ res = 0 ; $ curr_sum = 0 ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) { $ curr_sum += $ arr [ $ i ] ; $ res ++ ; if ( $ curr_sum > $ halfSum ) return $ res ; } return $ res ; } $ arr = array ( 3 , 1 , 7 , 1 ) ; $ n = sizeof ( $ arr ) ; echo minElements ( $ arr , $ n ) ; ? >