Maximum non overlapping Subset with sum greater than K – GeeksforGeeks

Given an array, arr[] and integer K, the task is to find the maximum number of non-overlapping subsets such that the sum of the subsets is strictly greater than K when you may also change the value of each element to the maximum value of the particular subset.

Examples:

Input: arr[]= {90, 80, 70, 60, 50, 100}, K = 180
Output: 2

Input: arr[] = {3, 2, 1}, K = 8
Output: 1

Approach: To solve the problem follow the below idea:

In order to form a maximum number of subsets we need to form a sequence with a minimum number of elements as well as the sum of values of elements should be greater than K. We start forming subsequences with elements having maximum value and changing the rest of the element value to the maximum value in the same subsequence.

Follow the steps mentioned below to implement the idea:  

• Sort the array arr[] in non-increasing order
• Take a pointer i initially at 0.
• Iterate over the array and form subset with arr[i] with minimum possible elements.
• Check if the elements already used + the elements required (d/arr[i] +1) for forming the current subset is less than or equal to the total number of elements then increase the subset formed and move pointer i to the next index.
• Else, a return number of subsequences is formed as there are not enough elements available to form more subsets.

Below is the implementation of the above approach:

Time Complexity: O(N * logN)
Auxiliary Space: O(1)

Related Articles: