text: Smallest subset with sum greater than all other elements | CPP program to find minimum number of elements such that their sum is greater than sum of remaining elements of the array . ; function to find minimum elements needed . ; calculating HALF of array sum ; sort the array in descending order . ; current sum greater than sum ; Driver function
code: #include <bits/stdc++.h> NEW_LINE #include <string.h> NEW_LINE using namespace std ; int minElements ( int arr [ ] , int n ) { int halfSum = 0 ; for ( int i = 0 ; i < n ; i ++ ) halfSum = halfSum + arr [ i ] ; halfSum = halfSum / 2 ; sort ( arr , arr + n , greater < int > ( ) ) ; int res = 0 , curr_sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) { curr_sum += arr [ i ] ; res ++ ; if ( curr_sum > halfSum ) return res ; } return res ; } int main ( ) { int arr [ ] = { 3 , 1 , 7 , 1 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << minElements ( arr , n ) << endl ; return 0 ; }