The smallest subset with sum greater than sum of all other elements

Reading time: 20 minutes | Coding time: 5 minutes

Given an array of non-negative integers. Our task is to find minimum number of elements(Subset) such that their sum should be greater than the sum of rest of the elements of the array.

Example 1:
arr[] = {5,2,9,1}
output: 1

Explanation:

{8} is the subset which have sum greater then other elements sum.

Example 2:
arr[] = {5,5,6,1}
output: 2

Explanation:
{5,5} have sum 10 which is greater then sum of other elements {6,1};

Algorithm

We explored two algorithms:

• A naive approach O(2^N)
• Greedy approach O(N log N)

Naive Approch

The Brute force approach is to find the sum of all the possible subsets and then compare sum with the sum of remaining elements.

CODE

#include <bits/stdc++.h>
using namespace std;

int main()
{
    std::vector<int> set{2, 1, 2};
    int set_size = set.size();
    unsigned int pow_set_size = pow(2, set_size);
    int counter, j;
    int total = 0;
    for (int i = 0; i < set_size; i++)
        total += set[i];

    for (counter = 0; counter < pow_set_size; counter++)
    {
        int sum = 0;
        int count = 0;
        for (j = 0; j < set_size; j++)
        {

            if (counter & (1 << j))
            {
                sum += set[j];
                count++;
            }
        }

        if (sum > (total - sum))
        {
            cout << "The smallest subset with sum greater with all other elements is " <<count;
            break;
        }
    }

    return 0;
}

Output

The smallest subset with sum greater with all other elements is 2

Greedy Approach

The better approch would be to add largest number to minimize the length of the subset. So we sort given array in descending order, then take elements from the largest, until we get strictly more than half of total sum of the given array.

Example:

arr[] = {5,2,9,1}
sort_descending(arr) => {9,5,2,1}
sum_arr = (9+5+2+1) = 17
subset sum with largest element {9} = 9;
subset_sum > (sum_arr-subset_sum) => 9 > (17-9) => 9 > 8 (ture)
print subset lenght i.e 1

Code

#include <bits/stdc++.h>
using namespace std;

int main() {
	vector <int> arr {5,2,9,1};
	int n = arr.size();
	int count  = 0;
	int sum  = 0;
	int tempSum = 0;
	
	for(int i=0;i<n;i++)
	    sum += arr[i];
	    
	sort(arr.begin(),arr.end(),greater<>()); 
	
	for(int i=0;i<n;i++)
	{
	    if(tempSum <= (sum - tempSum))
	    {
	        tempSum += arr[i];
	        count++;
	    }
	    else
	        break;
	}
	
	cout << "The smallest subset with sum greater with all other elements is " << count ;
	return 0;
}

Output:

The smallest subset with sum greater with all other elements is 1

Complexity

• Worst case time complexity:O(N log(N))
• Extra Space complexity: O(1)