Smallest subset of maximum sum possible by splitting array into two subsets

0 0 8 minutes read

Given an array arr[] consisting of N integers, the task is to print the smaller of the two subsets obtained by splitting the array into two subsets such that the sum of the smaller subset is maximized.

Examples:

Input: arr[] = {5, 3, 2, 4, 1, 2}
Output: 4 5
Explanation:
Split the array into two subsets as {4, 5} and {1, 2, 2, 3}.
The subset {4, 5} is of minimum length, i.e. 2, having maximum sum = 4 + 5 = 9.

Input: arr[] = {20, 15, 20, 50, 20}
Output: 15 50

Approach: The given problem can be solved by using Hashing and Sorting.
Follow the steps below to solve the problem:

Initialize a HashMap, say M, to store the frequency of each character of the array arr[].
Traverse the array arr[] and increment the count of every character in the HashMap M.
Initialize 2 variables, say S, and flag, to store the sum of the first subset and to store if an answer exists or not respectively.
Sort the array arr[] in ascending order.
Initialize an ArrayList, say ans, to store the elements of the resultant subset.
Traverse the array arr[] in reverse order and perform the following steps:
- Store the frequency of the current character in a variable, say F.
- If (F + ans.size()) is less than (N – (F + ans.size())) then append the element arr[i] in the ArrayList ans F number of times.
- Decrement the value of i by F.
- If the value of S is greater than the sum of the array elements, then mark the flag as true and then break.
After completing the above steps, if the value of flag is true, then print the ArrayList ans as the resultant subset. Otherwise, print -1.the

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to split array elements
// into two subsets having sum of
// the smaller subset maximized
static void findSubset(vector<int> arr)
{
   
    // Stores the size of the array
    int N = arr.size();
 
    // Stores the frequency
    // of array elements
    map<int,int> mp;
 
    // Stores the total
    // sum of the array
    int totSum = 0;
 
    // Stores the sum of
    // the resultant set
    int s = 0;
 
    // Stores if it is possible
    // to split the array that
    // satisfies the conditions
    int flag = 0;
 
    // Stores the elements
    // of the first subseta
    vector<int> ans;
 
    // Traverse the array arr[]
    for (int i = 0;
         i < arr.size(); i++) {
 
        // Increment total sum
        totSum += arr[i];
 
        // Increment count of arr[i]
        mp[arr[i]]=mp[arr[i]]+1;
      }  
 
    // Sort the array arr[]
    sort(arr.begin(),arr.end());
 
    // Stores the index of the
    // last element of the array
    int i = N - 1;
 
    // Traverse the array arr[]
    while (i >= 0) {
 
        // Stores the frequency
        // of arr[i]
        int frq = mp[arr[i]];
 
        // If frq + ans.size() is
        // at most remaining size
        if ((frq + ans.size())
            < (N - (frq + ans.size()))) 
        {
 
            for (int k = 0; k < frq; k++)
            {
 
                // Append arr[i] to ans
                ans.push_back(arr[i]);
 
                // Decrement totSum by arr[i]
                totSum -= arr[i];
 
                // Increment s by arr[i]
                s += arr[i];
 
                i--;
            }
        }
 
        // Otherwise, decrement i
        // by frq
        else {
            i -= frq;
        }
 
        // If s is greater
        // than totSum
        if (s > totSum) {
 
            // Mark flag 1
            flag = 1;
            break;
        }
    }
 
    // If flag is equal to 1
    if (flag == 1) {
 
        // Print the arrList ans
        for (i = ans.size() - 1;
             i >= 0; i--) {
 
            cout<<ans[i]<<" ";
        }
    }
 
    // Otherwise, print "-1"
    else {
        cout<<-1;
    }
}
 
// Driver Code
int main()
{
    vector<int> arr = { 5, 3, 2, 4, 1, 2 };
    findSubset(arr);
}
 
// This code is contributed by mohit kumar 29.

Java

// Java program for above approach
 
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG {
 
    // Function to split array elements
    // into two subsets having sum of
    // the smaller subset maximized
    static void findSubset(int[] arr)
    {
        // Stores the size of the array
        int N = arr.length;
 
        // Stores the frequency
        // of array elements
        Map<Integer, Integer> map
            = new HashMap<>();
 
        // Stores the total
        // sum of the array
        int totSum = 0;
 
        // Stores the sum of
        // the resultant set
        int s = 0;
 
        // Stores if it is possible
        // to split the array that
        // satisfies the conditions
        int flag = 0;
 
        // Stores the elements
        // of the first subset
        ArrayList<Integer> ans
            = new ArrayList<>();
 
        // Traverse the array arr[]
        for (int i = 0;
             i < arr.length; i++) {
 
            // Increment total sum
            totSum += arr[i];
 
            // Increment count of arr[i]
            map.put(arr[i],
                    map.getOrDefault(
                        arr[i], 0)
                        + 1);
        }
 
        // Sort the array arr[]
        Arrays.sort(arr);
 
        // Stores the index of the
        // last element of the array
        int i = N - 1;
 
        // Traverse the array arr[]
        while (i >= 0) {
 
            // Stores the frequency
            // of arr[i]
            int frq = map.get(arr[i]);
 
            // If frq + ans.size() is
            // at most remaining size
            if ((frq + ans.size())
                < (N - (frq + ans.size()))) {
 
                for (int k = 0; k < frq; k++) {
 
                    // Append arr[i] to ans
                    ans.add(arr[i]);
 
                    // Decrement totSum by arr[i]
                    totSum -= arr[i];
 
                    // Increment s by arr[i]
                    s += arr[i];
 
                    i--;
                }
            }
 
            // Otherwise, decrement i
            // by frq
            else {
                i -= frq;
            }
 
            // If s is greater
            // than totSum
            if (s > totSum) {
 
                // Mark flag 1
                flag = 1;
                break;
            }
        }
 
        // If flag is equal to 1
        if (flag == 1) {
 
            // Print the arrList ans
            for (i = ans.size() - 1;
                 i >= 0; i--) {
 
                System.out.print(
                    ans.get(i) + " ");
            }
        }
 
        // Otherwise, print "-1"
        else {
            System.out.print(-1);
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int[] arr = { 5, 3, 2, 4, 1, 2 };
        findSubset(arr);
    }
}

Python3

# Python 3 program for the above approach
from collections import defaultdict
 
# Function to split array elements
# into two subsets having sum of
# the smaller subset maximized
def findSubset(arr):
 
    # Stores the size of the array
    N = len(arr)
 
    # Stores the frequency
    # of array elements
    mp = defaultdict(int)
 
    # Stores the total
    # sum of the array
    totSum = 0
 
    # Stores the sum of
    # the resultant set
    s = 0
 
    # Stores if it is possible
    # to split the array that
    # satisfies the conditions
    flag = 0
 
    # Stores the elements
    # of the first subseta
    ans = []
 
    # Traverse the array arr[]
    for i in range(len(arr)):
 
        # Increment total sum
        totSum += arr[i]
 
        # Increment count of arr[i]
        mp[arr[i]] = mp[arr[i]]+1
 
    # Sort the array arr[]
    arr.sort()
 
    # Stores the index of the
    # last element of the array
    i = N - 1
 
    # Traverse the array arr[]
    while (i >= 0):
 
        # Stores the frequency
        # of arr[i]
        frq = mp[arr[i]]
 
        # If frq + ans.size() is
        # at most remaining size
        if ((frq + len(ans))
                < (N - (frq + len(ans)))):
 
            for k in range(frq):
 
                # Append arr[i] to ans
                ans.append(arr[i])
 
                # Decrement totSum by arr[i]
                totSum -= arr[i]
 
                # Increment s by arr[i]
                s += arr[i]
                i -= 1
 
        # Otherwise, decrement i
        # by frq
        else:
            i -= frq
 
        # If s is greater
        # than totSum
        if (s > totSum):
 
            # Mark flag 1
            flag = 1
            break
 
    # If flag is equal to 1
    if (flag == 1):
 
        # Print the arrList ans
        for i in range(len(ans) - 1, -1, -1):
 
            print(ans[i], end = " ")
 
    # Otherwise, print "-1"
    else:
        print(-1)
 
# Driver Code
if __name__ == "__main__":
 
    arr = [5, 3, 2, 4, 1, 2]
    findSubset(arr)
 
    # This code is contributed by ukasp.

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
   
// Function to split array elements
// into two subsets having sum of
// the smaller subset maximized
static void findSubset(List<int> arr)
{
   
    // Stores the size of the array
    int N = arr.Count;
    int i;
 
    // Stores the frequency
    // of array elements
    Dictionary<int,int> mp = new Dictionary<int,int>();
 
    // Stores the total
    // sum of the array
    int totSum = 0;
 
    // Stores the sum of
    // the resultant set
    int s = 0;
 
    // Stores if it is possible
    // to split the array that
    // satisfies the conditions
    int flag = 0;
 
    // Stores the elements
    // of the first subseta
    List<int> ans = new List<int>();
 
    // Traverse the array arr[]
    for (i = 0;
         i < arr.Count; i++) {
 
        // Increment total sum
        totSum += arr[i];
 
        // Increment count of arr[i]
        if(mp.ContainsKey(arr[i]))
         mp[arr[i]]=mp[arr[i]]+1;
        else
          mp.Add(arr[i],1);
      }  
 
    // Sort the array arr[]
    arr.Sort();
 
    // Stores the index of the
    // last element of the array
    i = N - 1;
 
    // Traverse the array arr[]
    while (i >= 0) {
 
        // Stores the frequency
        // of arr[i]
        int frq = mp[arr[i]];
 
        // If frq + ans.size() is
        // at most remaining size
        if ((frq + ans.Count)
            < (N - (frq + ans.Count))) 
        {
 
            for (int k = 0; k < frq; k++)
            {
 
                // Append arr[i] to ans
                ans.Add(arr[i]);
 
                // Decrement totSum by arr[i]
                totSum -= arr[i];
 
                // Increment s by arr[i]
                s += arr[i];
 
                i--;
            }
        }
 
        // Otherwise, decrement i
        // by frq
        else {
            i -= frq;
        }
 
        // If s is greater
        // than totSum
        if (s > totSum) {
 
            // Mark flag 1
            flag = 1;
            break;
        }
    }
 
    // If flag is equal to 1
    if (flag == 1) {
 
        // Print the arrList ans
        for (i = ans.Count - 1;
             i >= 0; i--) {
 
            Console.Write(ans[i]+" ");
        }
    }
 
    // Otherwise, print "-1"
    else {
        Console.Write(-1);
    }
}
 
// Driver Code
public static void Main()
{
    List<int> arr = new List<int>(){ 5, 3, 2, 4, 1, 2 };
    findSubset(arr);
}
 
}
 
// This code is contributed by ipg2016107.

Javascript

<script>
 
// Javascript program for the above approach
 
 
// Function to split array elements
// into two subsets having sum of
// the smaller subset maximized
function findSubset(arr)
{
   
    // Stores the size of the array
    var N = arr.length;
 
    // Stores the frequency
    // of array elements
    var mp = new Map();
 
    // Stores the total
    // sum of the array
    var totSum = 0;
 
    // Stores the sum of
    // the resultant set
    var s = 0;
 
    // Stores if it is possible
    // to split the array that
    // satisfies the conditions
    var flag = 0;
 
    // Stores the elements
    // of the first subseta
    var ans = [];
 
    // Traverse the array arr[]
    for (var i = 0;
         i < arr.length; i++) {
 
        // Increment total sum
        totSum += arr[i];
 
        // Increment count of arr[i]
        if(mp.has(arr[i]))
            mp.set(arr[i], mp.get(arr[i])+1)
        else
            mp.set(arr[i], 1);
      }  
 
    // Sort the array arr[]
    arr.sort((a,b)=> a-b)
 
    // Stores the index of the
    // last element of the array
    var i = N - 1;
 
    // Traverse the array arr[]
    while (i >= 0) {
 
        // Stores the frequency
        // of arr[i]
        var frq = mp.get(arr[i]);
 
        // If frq + ans.size() is
        // at most remaining size
        if ((frq + ans.length)
            < (N - (frq + ans.length))) 
        {
 
            for (var k = 0; k < frq; k++)
            {
 
                // Append arr[i] to ans
                ans.push(arr[i]);
 
                // Decrement totSum by arr[i]
                totSum -= arr[i];
 
                // Increment s by arr[i]
                s += arr[i];
 
                i--;
            }
        }
 
        // Otherwise, decrement i
        // by frq
        else {
            i -= frq;
        }
 
        // If s is greater
        // than totSum
        if (s > totSum) {
 
            // Mark flag 1
            flag = 1;
            break;
        }
    }
 
    // If flag is equal to 1
    if (flag == 1) {
 
        // Print the arrList ans
        for (i = ans.length - 1;
             i >= 0; i--) {
 
            document.write( ans[i] + " ");
        }
    }
 
    // Otherwise, print "-1"
    else {
        document.write(-1);
    }
}
 
// Driver Code
var arr = [5, 3, 2, 4, 1, 2 ];
findSubset(arr);
 
// This code is contributed by rutvik_56.
</script>

Output:

4 5

Time Complexity: O(N*log N)
Auxiliary Space: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!