Dada una array arr[] que consta de N enteros, la tarea es verificar si es posible dividir los enteros en dos subconjuntos de igual longitud, de modo que todas las repeticiones de cualquier elemento de la array pertenezcan al mismo subconjunto. Si es cierto, escriba “Sí” . De lo contrario, escriba “No” .
Ejemplos:
Entrada: arr[] = {2, 1, 2, 3}
Salida: Sí
Explicación:
Una forma posible de dividir la array es {1, 3} y {2, 2}Entrada: arr[] = {1, 1, 1, 1}
Salida: No
Enfoque ingenuo: el enfoque más simple para resolver el problema es probar todas las combinaciones posibles de dividir la array en dos subconjuntos iguales. Para cada combinación, compruebe si cada repetición pertenece a uno solo de los dos conjuntos o no. Si se encuentra que es cierto, escriba «Sí» . De lo contrario, escriba “No” .
Complejidad de tiempo: O(2 N ), donde N es el tamaño del entero dado.
Espacio Auxiliar: O(N)
Enfoque eficiente: el enfoque anterior se puede optimizar almacenando la frecuencia de todos los elementos de la array dada en una array freq[] . Para que los elementos se dividan en dos conjuntos iguales, N/2 elementos deben estar presentes en cada conjunto. Por lo tanto, para dividir la array dada arr[] en 2 partes iguales, debe haber algún subconjunto de enteros en freq[] que tenga una suma N /2 . Siga los pasos a continuación para resolver el problema:
- Almacene la frecuencia de cada elemento en el Mapa M.
- Ahora, cree una array auxiliar aux[] e insértela en ella, todas las frecuencias almacenadas desde el Mapa .
- El problema dado se reduce a encontrar un subconjunto en la array aux[] que tenga una suma N/2 dada .
- Si existe algún subconjunto de este tipo en el paso anterior, imprima «Sí» . De lo contrario, escriba “No” .
A continuación se muestra la implementación del enfoque anterior:
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 subset
bool 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 sets
void 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 approach
import 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 approach
from 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 subset
def 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 sets
def 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 Code
if __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
// approach
using 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 subset
static 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 sets
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)
{
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 code
static 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 subset
function 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 cells
for ( 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 sets
function 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>
Producción:
Yes
Complejidad de tiempo: O(N*M), donde N es el tamaño de la array y M es el recuento total de elementos distintos en la array dada.
Espacio Auxiliar: O(N)