Smallest Subset Array

The task is to find the subset of array elements such that their sum should be greater than the half sum of the rest of the elements of the array. Also, subset array elements in ascending order.

Example 1:

**Input** [1, 2, 5, 10, 20, 1]
**Half Sum** 19
**Result** [20]

Example 2:

**Input** [1, 2, 5, 10, 20, 3, 7]
**Half Sum** 24
**Result** [1, 3, 20]

Solutions

The problem is a variant of the subset sum problem, which is a well-known problem in computer science. The subset sum problem is NP-complete, which means that there is no known algorithm that can solve all instances of the problem in polynomial time (such as O(n)).

Approach – Greedy Technique

The approach is to take the largest elements from the array, in that way we can decrease the size of the subset that has sum greater than the sum of rest of the elements of the array, so we sort the array in descending order, then take the largest elements, until we get strictly more than half of total sum of the given array.

Steps

1. First calculate sum of all elements of an array.

2. Take sum half.

3. Sort an array element.

4. Run loop till when sum of array elements is greater than the half sum of an array elements. If found then create a new subset array and copy elements in ascending order and return it, else return original array.

    public int[] Subset(int[] nums)
    {

        long sum = 0;
        for (int i = 0; i < nums.Length; i++)
        {
            sum += nums[i];
        }

        long target = sum / 2;

        sum = 0;
        Array.Sort(nums);

        for (int i = nums.Length - 1; i >= 0; i--)
        {
            sum += nums[i];
            if (sum > target)
            {
                var result = new int[nums.Length - i];
                for (int j = nums.Length - 1; j >= i; j--)
                {
                    result[j - i] = nums[j];
                }
                return result;
            }

        }

        return nums;
    }

Complexity

• Time complexity: O(n log n)

• Space complexity: O(k)

Here, k is size of subset array.