Given an array arr[] consisting of N integers, the task is to check if it is possible to split the integers into two equal length subsets such that all repetitions of any array element belong to the same subset. If found to be true, print “Yes”. Otherwise, print “No”.
Examples:
Input: arr[] = {2, 1, 2, 3}
Output: Yes
Explanation:
One possible way of dividing the array is {1, 3} and {2, 2}Input: arr[] = {1, 1, 1, 1}
Output: No
Naive Approach: The simplest approach to solve the problem is to try all possible combinations of splitting the array into two equal subsets. For each combination, check whether every repetition belongs to only one of the two sets or not. If found to be true, then print “Yes”. Otherwise, print “No”.
Time Complexity: O(2N), where N is the size of the given integer.
Auxiliary Space: O(N)
Efficient Approach: The above approach can be optimized by storing the frequency of all elements of the given array in an array freq[]. For elements to be divided into two equal sets, N/2 elements must be present in each set. Therefore, to divide the given array arr[] into 2 equal parts, there must be some subset of integers in freq[] having sum N/2. Follow the steps below to solve the problem:
- Store the frequency of each element in Map M.
- Now, create an auxiliary array aux[] and insert it into it, all the frequencies stored from the Map.
- The given problem reduces to finding a subset in the array aux[] having a given sum N/2.
- If there exists any such subset in the above step, then print “Yes”. Otherwise, print “No”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to create the frequency// array of the given array arr[]vector<int> findSubsets(vector<int> arr, int N){ // Hashmap to store the // frequencies map<int,int> M; // Store freq for each element for (int i = 0; i < N; i++) { M[arr[i]]++; } // Get the total frequencies vector<int> subsets; int I = 0; // Store frequencies in // subset[] array for(auto playerEntry = M.begin(); playerEntry != M.end(); playerEntry++) { subsets.push_back(playerEntry->second); I++; } // Return frequency array return subsets;} // Function to check is sum // N/2 can be formed using // some subsetbool subsetSum(vector<int> subsets, int N, int target){ // dp[i][j] store the answer to // form sum j using 1st i elements bool dp[N + 1][target + 1]; // Initialize dp[][] with true for (int i = 0; i < N + 1; i++) dp[i][0] = true; // Fill the subset table in the // bottom up manner for (int i = 1; i <= N; i++) { for (int j = 1; j <= target; j++) { dp[i][j] = dp[i - 1][j]; // If current element is // less than j if (j >= subsets[i - 1]) { // Update current state dp[i][j] |= dp[i - 1][j - subsets[i - 1]]; } } } // Return the result return dp[N][target];} // Function to check if the given// array can be split into required setsvoid divideInto2Subset(vector<int> arr, int N){ // Store frequencies of arr[] vector<int> subsets = findSubsets(arr, N); // If size of arr[] is odd then // print "Yes" if ((N) % 2 == 1) { cout << "No" << endl; return; } int subsets_size = subsets.size(); // Check if answer is true or not bool isPossible = subsetSum(subsets, subsets_size, N / 2); // Print the result if (isPossible) { cout << "Yes" << endl; } else { cout << "No" << endl; }}int main(){ // Given array arr[] vector<int> arr{2, 1, 2, 3}; int N = arr.size(); // Function Call divideInto2Subset(arr, N); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG { // Function to create the frequency // array of the given array arr[] private static int[] findSubsets(int[] arr) { // Hashmap to store the frequencies HashMap<Integer, Integer> M = new HashMap<>(); // Store freq for each element for (int i = 0; i < arr.length; i++) { M.put(arr[i], M.getOrDefault(arr[i], 0) + 1); } // Get the total frequencies int[] subsets = new int[M.size()]; int i = 0; // Store frequencies in subset[] array for ( Map.Entry<Integer, Integer> playerEntry : M.entrySet()) { subsets[i++] = playerEntry.getValue(); } // Return frequency array return subsets; } // Function to check is sum N/2 can be // formed using some subset private static boolean subsetSum(int[] subsets, int target) { // dp[i][j] store the answer to // form sum j using 1st i elements boolean[][] dp = new boolean[subsets.length + 1][target + 1]; // Initialize dp[][] with true for (int i = 0; i < dp.length; i++) dp[i][0] = true; // Fill the subset table in the // bottom up manner for (int i = 1; i <= subsets.length; i++) { for (int j = 1; j <= target; j++) { dp[i][j] = dp[i - 1][j]; // If current element is // less than j if (j >= subsets[i - 1]) { // Update current state dp[i][j] |= dp[i - 1][j - subsets[i - 1]]; } } } // Return the result return dp[subsets.length][target]; } // Function to check if the given // array can be split into required sets public static void divideInto2Subset(int[] arr) { // Store frequencies of arr[] int[] subsets = findSubsets(arr); // If size of arr[] is odd then // print "Yes" if ((arr.length) % 2 == 1) { System.out.println("No"); return; } // Check if answer is true or not boolean isPossible = subsetSum(subsets, arr.length / 2); // Print the result if (isPossible) { System.out.println("Yes"); } else { System.out.println("No"); } } // Driver Code public static void main(String[] args) { // Given array arr[] int[] arr = { 2, 1, 2, 3 }; // Function Call divideInto2Subset(arr); }}// This code is contributed by divyesh072019 |
Python3
# Python3 program for the # above approachfrom collections import defaultdict# Function to create the # frequency array of the # given array arr[]def findSubsets(arr): # Hashmap to store # the frequencies M = defaultdict (int) # Store freq for each element for i in range (len(arr)): M[arr[i]] += 1 # Get the total frequencies subsets = [0] * len(M) i = 0 # Store frequencies in # subset[] array for j in M: subsets[i] = M[j] i += 1 # Return frequency array return subsets# Function to check is # sum N/2 can be formed # using some subsetdef subsetSum(subsets, target): # dp[i][j] store the answer to # form sum j using 1st i elements dp = [[0 for x in range(target + 1)] for y in range(len(subsets) + 1)] # Initialize dp[][] with true for i in range(len(dp)): dp[i][0] = True # Fill the subset table in the # bottom up manner for i in range(1, len(subsets) + 1): for j in range(1, target + 1): dp[i][j] = dp[i - 1][j] # If current element is # less than j if (j >= subsets[i - 1]): # Update current state dp[i][j] |= (dp[i - 1][j - subsets[i - 1]]) # Return the result return dp[len(subsets)][target]# Function to check if the given# array can be split into required setsdef divideInto2Subset(arr): # Store frequencies of arr[] subsets = findSubsets(arr) # If size of arr[] is odd then # print "Yes" if (len(arr) % 2 == 1): print("No") return # Check if answer is true or not isPossible = subsetSum(subsets, len(arr) // 2) # Print the result if (isPossible): print("Yes") else : print("No")# Driver Codeif __name__ == "__main__": # Given array arr arr = [2, 1, 2, 3] # Function Call divideInto2Subset(arr)# This code is contributed by Chitranayal |
C#
// C# program for the above // approachusing System;using System.Collections.Generic; class GFG{ // Function to create the frequency// array of the given array arr[]static int[] findSubsets(int[] arr){ // Hashmap to store the // frequencies Dictionary<int, int> M = new Dictionary<int, int>(); // Store freq for each element for (int i = 0; i < arr.Length; i++) { if(M.ContainsKey(arr[i])) { M[arr[i]]++; } else { M[arr[i]] = 1; } } // Get the total frequencies int[] subsets = new int[M.Count]; int I = 0; // Store frequencies in // subset[] array foreach(KeyValuePair<int, int> playerEntry in M) { subsets[I] = playerEntry.Value; I++; } // Return frequency array return subsets;}// Function to check is sum // N/2 can be formed using // some subsetstatic bool subsetSum(int[] subsets, int target){ // dp[i][j] store the answer to // form sum j using 1st i elements bool[,] dp = new bool[subsets.Length + 1, target + 1]; // Initialize dp[][] with true for (int i = 0; i < dp.GetLength(0); i++) dp[i, 0] = true; // Fill the subset table in the // bottom up manner for (int i = 1; i <= subsets.Length; i++) { for (int j = 1; j <= target; j++) { dp[i, j] = dp[i - 1, j]; // If current element is // less than j if (j >= subsets[i - 1]) { // Update current state dp[i, j] |= dp[i - 1, j - subsets[i - 1]]; } } } // Return the result return dp[subsets.Length, target];}// Function to check if the given// array can be split into required setsstatic void divideInto2Subset(int[] arr){ // Store frequencies of arr[] int[] subsets = findSubsets(arr); // If size of arr[] is odd then // print "Yes" if ((arr.Length) % 2 == 1) { Console.WriteLine("No"); return; } // Check if answer is true or not bool isPossible = subsetSum(subsets, arr.Length / 2); // Print the result if (isPossible) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); }} // Driver codestatic void Main() { // Given array arr[] int[] arr = {2, 1, 2, 3}; // Function Call divideInto2Subset(arr);}}// This code is contributed by divyeshrabadiya07 |
Javascript
<script>// JavaScript program for the above approach// Function to create the frequency// array of the given array arr[]function findSubsets( arr, N){ // Hashmap to store the // frequencies let M = new Map(); // Store freq for each element for (let i = 0; i < N; i++) { if(M[arr[i]]) M[arr[i]]++; else M[arr[i]] = 1 } // Get the total frequencies let subsets = []; let I = 0; // Store frequencies in // subset[] array for(var it in M) { subsets.push(M[it]); } // Return frequency array return subsets;} // Function to check is sum // N/2 can be formed using // some subsetfunction subsetSum( subsets, N, target){ // dp[i][j] store the answer to // form sum j using 1st i elements var dp = [], H = N+1; // 4 rows W = target+1; // of 6 cellsfor ( var y = 0; y < H; y++ ) { dp[ y ] = []; for ( var x = 0; x < W; x++ ) { dp[ y ][ x ] = false; }} // Initialize dp[][] with true for (let i = 0; i < N + 1; i++) dp[i][0] = true; // Fill the subset table in the // bottom up manner for (let i = 1; i <= N; i++) { for (let j = 1; j <= target; j++) { dp[i][j] = dp[i - 1][j]; // If current element is // less than j if (j >= subsets[i - 1]) { // Update current state dp[i][j] |= dp[i - 1][j - subsets[i - 1]]; } } } // Return the result return dp[N][target];} // Function to check if the given// array can be split into required setsfunction divideInto2Subset( arr, N){ // Store frequencies of arr[] let subsets = findSubsets(arr, N); // If size of arr[] is odd then // print "Yes" if ((N) % 2 == 1) { document.write( "No<br>"); return; } let subsets_size = subsets.length; // Check if answer is true or not let isPossible = subsetSum(subsets, subsets_size, Math.floor(N / 2)); // Print the result if (isPossible) { document.write( "Yes<br>"); } else { document.write( "No<br>"); }} // Given array arr[] let arr = [2, 1, 2, 3]; let N = arr.length; // Function Call divideInto2Subset(arr, N);</script> |
Output:
Yes
Time Complexity: O(N*Target) where target is N/2
Auxiliary Space: O(N*Target)
Efficient Approach : Space optimization
In previous approach the current computation Dp[i][j] is only depend upon the current row and previous row of DP. So we can optimize the space by using a 1D array to store these computations.
Implementation Steps:
- Create a DP array of size target+1 and initialize it with False.
- Set base case by initializing dp[0] = true.
- Now iterate over subproblems with the help of nested loops and get the current value from the previous computations.
- At last return final answer stored in dp[target].
Implementation:
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;// Function to create the frequency// array of the given array arr[]vector<int> findSubsets(vector<int>& arr, int N){ // Hashmap to store the // frequencies map<int,int> M; // Store freq for each element for (int i = 0; i < N; i++) { M[arr[i]]++; } // Get the total frequencies vector<int> subsets; // Store frequencies in // subset[] array for(auto playerEntry = M.begin(); playerEntry != M.end(); playerEntry++) { subsets.push_back(playerEntry->second); } // Return frequency array return subsets;} // Function to check is sum // N/2 can be formed using // some subsetbool subsetSum(vector<int>& subsets, int N, int target){ // dp[] store the answer to // form sum j using 1st i elements bool dp[target + 1]; // Initialize dp[] with true memset(dp, false, sizeof(dp)); dp[0] = true; // Fill the subset table in the // bottom up manner for (int i = 1; i <= N; i++) { for (int j = target; j >= 1; j--) { // If current element is // less than j if (j >= subsets[i - 1]) { // Update current state dp[j] |= dp[j - subsets[i - 1]]; } } } // Return the result return dp[target];} // Function to check if the given// array can be split into required setsvoid divideInto2Subset(vector<int>& arr, int N){ // Store frequencies of arr[] vector<int> subsets = findSubsets(arr, N); // If size of arr[] is odd then // print "No" if ((N) % 2 == 1) { cout << "No" << endl; return; } int subsets_size = subsets.size(); // Check if answer is true or not bool isPossible = subsetSum(subsets, subsets_size, N / 2); // Print the result if (isPossible) { cout << "Yes" << endl; } else { cout << "No" << endl; }}int main(){ // Given array arr[] vector<int> arr{2, 1, 2, 3}; int N = arr.size(); // Function Call divideInto2Subset(arr, N); return 0;}// this code is contributed by bhardwajji |
Java
import java.util.*;public class Main { // Function to create the frequency // array of the given array arr[] static List<Integer> findSubsets(List<Integer> arr, int N) { // Hashmap to store the // frequencies Map<Integer, Integer> M = new HashMap<>(); // Store freq for each element for (int i = 0; i < N; i++) { int element = arr.get(i); if (M.containsKey(element)) { M.put(element, M.get(element) + 1); } else { M.put(element, 1); } } // Get the total frequencies List<Integer> subsets = new ArrayList<>(); // Store frequencies in // subset[] array for (Map.Entry<Integer, Integer> entry : M.entrySet()) { subsets.add(entry.getValue()); } // Return frequency array return subsets; } // Function to check is sum // N/2 can be formed using // some subset static boolean subsetSum(List<Integer> subsets, int N, int target) { // dp[] store the answer to // form sum j using 1st i elements boolean[] dp = new boolean[target + 1]; // Initialize dp[] with true Arrays.fill(dp, false); dp[0] = true; // Fill the subset table in the // bottom up manner for (int i = 1; i <= N; i++) { for (int j = target; j >= 1; j--) { // If current element is // less than j if (j >= subsets.get(i - 1)) { // Update current state dp[j] |= dp[j - subsets.get(i - 1)]; } } } // Return the result return dp[target]; } // Function to check if the given // array can be split into required sets static void divideInto2Subset(List<Integer> arr, int N) { // Store frequencies of arr[] List<Integer> subsets = findSubsets(arr, N); // If size of arr[] is odd then // print "No" if ((N) % 2 == 1) { System.out.println("No"); return; } int subsets_size = subsets.size(); // Check if answer is true or not boolean isPossible = subsetSum(subsets, subsets_size, N / 2); // Print the result if (isPossible) { System.out.println("Yes"); } else { System.out.println("No"); } } public static void main(String[] args) { // Given array arr[] List<Integer> arr = new ArrayList<>(Arrays.asList(2, 1, 2, 3)); int N = arr.size(); // Function Call divideInto2Subset(arr, N); }} |
Python3
# Python 3 program for above approach# Function to create the frequency# array of the given array arr[]def findSubsets(arr, N): # Hashmap to store the # frequencies M = {} # Store freq for each element for i in range(N): if arr[i] not in M: M[arr[i]] = 1 else: M[arr[i]] += 1 # Get the total frequencies subsets = [] # Store frequencies in # subset[] array for playerEntry in M: subsets.append(M[playerEntry]) # Return frequency array return subsets# Function to check is sum# N/2 can be formed using# some subsetdef subsetSum(subsets, N, target): # dp[] store the answer to # form sum j using 1st i elements dp = [False]*(target+1) # Initialize dp[] with true dp[0] = True # Fill the subset table in the # bottom up manner for i in range(1, N+1): for j in range(target, 0, -1): # If current element is # less than j if j >= subsets[i - 1]: # Update current state dp[j] |= dp[j - subsets[i - 1]] # Return the result return dp[target]# Function to check if the given# array can be split into required setsdef divideInto2Subset(arr, N): # Store frequencies of arr[] subsets = findSubsets(arr, N) # If size of arr[] is odd then # print "No" if (N) % 2 == 1: print("No") return subsets_size = len(subsets) # Check if answer is true or not isPossible = subsetSum(subsets, subsets_size, N // 2) # Print the result if isPossible: print("Yes") else: print("No")# Given array arr[]arr = [2, 1, 2, 3]N = len(arr)# Function CalldivideInto2Subset(arr, N) |
C#
// C# program for above approach// Function to create the frequency// array of the given array arr[]using System;using System.Collections.Generic;public class Program { public static List<int> findSubsets(List<int> arr, int N) { // Dictionary to store the // frequencies Dictionary<int, int> M = new Dictionary<int, int>(); // Store freq for each element for (int i = 0; i < N; i++) { if (!M.ContainsKey(arr[i])) { M[arr[i]] = 1; } else { M[arr[i]] += 1; } } // Get the total frequencies List<int> subsets = new List<int>(); // Store frequencies in // subset[] array foreach (KeyValuePair<int, int> playerEntry in M) { subsets.Add(playerEntry.Value); } // Return frequency array return subsets; } // Function to check is sum // N/2 can be formed using // some subset public static bool subsetSum(List<int> subsets, int N, int target) { bool[] dp = new bool[target+1]; // dp[] store the answer to // form sum j using 1st i elements // Initialize dp[] with true dp[0] = true; // Fill the subset table in the // bottom up manner for (int i = 1; i <= N; i++) { for (int j = target; j > 0; j--) { // If current element is // less than j if (j >= subsets[i - 1]) { // Update current state dp[j] |= dp[j - subsets[i - 1]]; } } } // Return the result return dp[target]; } // Function to check if the given // array can be split into required sets public static void divideInto2Subset(List<int> arr, int N) { // Store frequencies of List List<int> subsets = findSubsets(arr, N); // If size of arr[] is odd then // print "No" if (N % 2 == 1) { Console.WriteLine("No"); return; } int subsets_size = subsets.Count; // Check if answer is true or not bool isPossible = subsetSum(subsets, subsets_size, N / 2); // Print the result if (isPossible) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } } public static void Main(string[] args) { // Given List List<int> arr = new List<int>() {2, 1, 2, 3}; int N = arr.Count; // Function Call divideInto2Subset(arr, N); }}// This code is cintributed by shiv1o43g |
Javascript
// Javascript code addition // Function to create the frequency array of the given array arr[]function findSubsets(arr, N) { // Hashmap to store the frequencies let M = new Map(); // Store freq for each element for (let i = 0; i < N; i++) { if (M.has(arr[i])) { M.set(arr[i], M.get(arr[i]) + 1); } else { M.set(arr[i], 1); } } // Get the total frequencies let subsets = []; // Store frequencies in subset[] array for (let [key, value] of M) { subsets.push(value); } // Return frequency array return subsets;}// Function to check is sum N/2 can be formed using some subsetfunction subsetSum(subsets, N, target) { // dp[] store the answer to form sum j using 1st i elements let dp = new Array(target + 1).fill(false); dp[0] = true; // Fill the subset table in the bottom up manner for (let i = 1; i <= N; i++) { for (let j = target; j >= 1; j--) { // If current element is less than j if (j >= subsets[i - 1]) { // Update current state dp[j] |= dp[j - subsets[i - 1]]; } } } // Return the result return dp[target];}// Function to check if the given array can be split into required setsfunction divideInto2Subset(arr, N) { // Store frequencies of arr[] let subsets = findSubsets(arr, N); // If size of arr[] is odd then print "No" if (N % 2 === 1) { console.log("No"); return; } let subsets_size = subsets.length; // Check if answer is true or not let isPossible = subsetSum(subsets, subsets_size, N / 2); // Print the result if (isPossible) { console.log("Yes"); } else { console.log("No"); }}// Given array arr[]let arr = [2, 1, 2, 3];let N = arr.length;// Function CalldivideInto2Subset(arr, N);// The code is contributed by Nidhi goel. |
Output
Yes
Time Complexity: O(N*Target) where target is N/2
Auxiliary Space: O(Target)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
