Dada una array de enteros arr[] que consta de N enteros, la tarea es verificar si es posible dividir la array dada en K subconjuntos no vacíos de igual suma, de modo que cada elemento de la array sea parte de un solo subconjunto.
Ejemplos:
Entrada: arr[] = {2, 1, 4, 5, 6}, K = 3
Salida: Sí
Explicación:
Los subconjuntos posibles de la array dada son {2, 4}, (1, 5} y {6}
Entrada: arr [] = {2, 1, 5, 5, 6}, K = 3
Salida: No
Para el enfoque recursivo, consulte Partición de un conjunto en K subconjuntos con igual suma .
Enfoque:
siga los pasos a continuación para resolver el problema:
- La idea es usar máscara para determinar el estado actual. El estado actual nos dirá sobre el subconjunto ya formado (qué números ya están seleccionados).
Por ejemplo: arr[] = [2, 1, 4, 3, 5, 6, 2], mask = (1100101), lo que significa que { 2, 1, 5, 2 } ya están seleccionados en la máscara actual. - Para cualquier máscara de estado actual, se le agregará el j -ésimo elemento en función de las dos condiciones siguientes:
- El j -ésimo bit no está configurado en la máscara ( máscara&(1<<j) == 0 )
- sum (máscara) + arr[j] <= target (donde target = (Suma de los elementos de la array) / K)
- Mantenga una tabla dp[] tal que dp[i] almacene la suma de elementos en la máscara i . Entonces, las transiciones dp serán:
dp[yo | (1 << j)] = (dp[i] + arr[j]) % objetivo
Ilustración:
arr [ ] = [4, 3, 2, 3, 5, 2, 1], K = 4, tar = 5
dp[“1100101”] implica que se eligen { 4, 3, 5, 1 } Por lo
tanto, Sum = 4 + 3 + 5 + 1 = 13, 13 % 5 = 3.
Por lo tanto, dp[“1100101”] = 3
Si dp[“11111…1111”] == 0 entonces eso significa que podemos encontrar la solución.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to check if the
// given array can be partitioned
// into K subsets with equal sum
#include <bits/stdc++.h>
using namespace std;
// Function to check whether
// K required partitions
// are possible or not
bool isKPartitionPossible(int arr[],
int N, int K)
{
if (K == 1)
// Return true as the
// entire array is the
// answer
return true;
// If total number of
// partitions exceeds
// size of the array
if (N < K)
return false;
int sum = 0;
for (int i = 0; i < N; i++)
sum += arr[i];
// If the array sum is not
// divisible by K
if (sum % K != 0)
// No such partitions are
// possible
return false;
// Required sum of
// each subset
int target = sum / K;
// Initialize dp array with -1
int dp[(1 << 15)];
for (int i = 0; i < (1 << N); i++)
dp[i] = -1;
// Sum of empty subset
// is zero
dp[0] = 0;
// Iterate over all subsets/masks
for (int mask = 0; mask < (1 << N); mask++) {
// if current mask is invalid, continue
if (dp[mask] == -1)
continue;
// Iterate over all array elements
for (int i = 0; i < N; i++) {
// Check if the current element
// can be added to the current
// subset/mask
if (!(mask & (1 << i))
&& dp[mask]
+ arr[i]
<= target) {
// transition
dp[mask | (1 << i)]
= (dp[mask]
+ arr[i])
% target;
}
}
}
if (dp[(1 << N) - 1] == 0)
return true;
else
return false;
}
// Driver Code
int main()
{
int arr[] = { 2, 1, 4, 5, 3, 3 };
int N = sizeof(arr) / sizeof(arr[0]);
int K = 3;
if (isKPartitionPossible(arr, N, K)) {
cout << "Partitions into equal ";
cout << "sum is possible.\n";
}
else {
cout << "Partitions into equal ";
cout << "sum is not possible.\n";
}
}
Java
// Java program to check if the
// given array can be partitioned
// into K subsets with equal sum
import java.util.*;
class GFG{
// Function to check whether
// K required partitions
// are possible or not
static boolean isKPartitionPossible(int arr[],
int N, int K)
{
if (K == 1)
// Return true as the
// entire array is the
// answer
return true;
// If total number of
// partitions exceeds
// size of the array
if (N < K)
return false;
int sum = 0;
for(int i = 0; i < N; i++)
sum += arr[i];
// If the array sum is not
// divisible by K
if (sum % K != 0)
// No such partitions are
// possible
return false;
// Required sum of
// each subset
int target = sum / K;
// Initialize dp array with -1
int []dp = new int[(1 << 15)];
for(int i = 0; i < (1 << N); i++)
dp[i] = -1;
// Sum of empty subset
// is zero
dp[0] = 0;
// Iterate over all subsets/masks
for(int mask = 0; mask < (1 << N); mask++)
{
// if current mask is invalid, continue
if (dp[mask] == -1)
continue;
// Iterate over all array elements
for(int i = 0; i < N; i++)
{
// Check if the current element
// can be added to the current
// subset/mask
if (((mask & (1 << i)) == 0) &&
dp[mask] + arr[i] <= target)
{
// Transition
dp[mask | (1 << i)] = (dp[mask] +
arr[i]) %
target;
}
}
}
if (dp[(1 << N) - 1] == 0)
return true;
else
return false;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 2, 1, 4, 5, 3, 3 };
int N = arr.length;
int K = 3;
if (isKPartitionPossible(arr, N, K))
{
System.out.print("Partitions into equal ");
System.out.print("sum is possible.\n");
}
else
{
System.out.print("Partitions into equal ");
System.out.print("sum is not possible.\n");
}
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program to check if the
# given array can be partitioned
# into K subsets with equal sum
# Function to check whether
# K required partitions
# are possible or not
def isKPartitionPossible(arr, N, K):
if (K == 1):
# Return true as the
# entire array is the
# answer
return True
# If total number of
# partitions exceeds
# size of the array
if (N < K):
return False
sum = 0
for i in range(N):
sum += arr[i]
# If the array sum is not
# divisible by K
if (sum % K != 0):
# No such partitions are
# possible
return False
# Required sum of
# each subset
target = sum / K
# Initialize dp array with -1
dp = [0 for i in range(1 << 15)]
for i in range((1 << N)):
dp[i] = -1
# Sum of empty subset
# is zero
dp[0] = 0
# Iterate over all subsets/masks
for mask in range((1 << N)):
# If current mask is invalid,
# continue
if (dp[mask] == -1):
continue
# Iterate over all array elements
for i in range(N):
# Check if the current element
# can be added to the current
# subset/mask
if ((mask & (1 << i) == 0) and
dp[mask] + arr[i] <= target):
# Transition
dp[mask | (1 << i)] = ((dp[mask] +
arr[i]) %
target)
if (dp[(1 << N) - 1] == 0):
return True
else:
return False
# Driver Code
if __name__ == '__main__':
arr = [ 2, 1, 4, 5, 3, 3 ]
N = len(arr)
K = 3
if (isKPartitionPossible(arr, N, K)):
print("Partitions into equal "\
"sum is possible.")
else:
print("Partitions into equal sum "\
"is not possible.")
# This code is contributed by Surendra_Gangwar
C#
// C# program to check if the
// given array can be partitioned
// into K subsets with equal sum
using System;
class GFG{
// Function to check whether
// K required partitions
// are possible or not
static bool isKPartitionPossible(int []arr,
int N, int K)
{
if (K == 1)
// Return true as the
// entire array is the
// answer
return true;
// If total number of
// partitions exceeds
// size of the array
if (N < K)
return false;
int sum = 0;
for(int i = 0; i < N; i++)
sum += arr[i];
// If the array sum is not
// divisible by K
if (sum % K != 0)
// No such partitions are
// possible
return false;
// Required sum of
// each subset
int target = sum / K;
// Initialize dp array with -1
int []dp = new int[(1 << 15)];
for(int i = 0; i < (1 << N); i++)
dp[i] = -1;
// Sum of empty subset
// is zero
dp[0] = 0;
// Iterate over all subsets/masks
for(int mask = 0; mask < (1 << N); mask++)
{
// If current mask is invalid, continue
if (dp[mask] == -1)
continue;
// Iterate over all array elements
for(int i = 0; i < N; i++)
{
// Check if the current element
// can be added to the current
// subset/mask
if (((mask & (1 << i)) == 0) &&
dp[mask] + arr[i] <= target)
{
// Transition
dp[mask | (1 << i)] = (dp[mask] +
arr[i]) %
target;
}
}
}
if (dp[(1 << N) - 1] == 0)
return true;
else
return false;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 2, 1, 4, 5, 3, 3 };
int N = arr.Length;
int K = 3;
if (isKPartitionPossible(arr, N, K))
{
Console.Write("Partitions into equal ");
Console.Write("sum is possible.\n");
}
else
{
Console.Write("Partitions into equal ");
Console.Write("sum is not possible.\n");
}
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// JavaScript program to check if the
// given array can be partitioned
// into K subsets with equal sum
// Function to check whether
// K required partitions
// are possible or not
function isKPartitionPossible(arr, N, K)
{
if (K == 1)
// Return true as the
// entire array is the
// answer
return true;
// If total number of
// partitions exceeds
// size of the array
if (N < K)
return false;
let sum = 0;
for(let i = 0; i < N; i++)
sum += arr[i];
// If the array sum is not
// divisible by K
if (sum % K != 0)
// No such partitions are
// possible
return false;
// Required sum of
// each subset
let target = sum / K;
// Initialize dp array with -1
let dp = Array.from({length: (1 << 15)}, (_, i) => 0);
for(let i = 0; i < (1 << N); i++)
dp[i] = -1;
// Sum of empty subset
// is zero
dp[0] = 0;
// Iterate over all subsets/masks
for(let mask = 0; mask < (1 << N); mask++)
{
// if current mask is invalid, continue
if (dp[mask] == -1)
continue;
// Iterate over all array elements
for(let i = 0; i < N; i++)
{
// Check if the current element
// can be added to the current
// subset/mask
if (((mask & (1 << i)) == 0) &&
dp[mask] + arr[i] <= target)
{
// Transition
dp[mask | (1 << i)] = (dp[mask] +
arr[i]) %
target;
}
}
}
if (dp[(1 << N) - 1] == 0)
return true;
else
return false;
}
// Driver Code
let arr = [ 2, 1, 4, 5, 3, 3 ];
let N = arr.length;
let K = 3;
if (isKPartitionPossible(arr, N, K))
{
document.write("Partitions into equal ");
document.write("sum is possible.\n");
}
else
{
document.write("Partitions into equal ");
document.write("sum is not possible.\n");
}
</script>
Producción:
Partitions into equal sum is possible.
Complejidad Temporal: O (N * 2 N )
Espacio Auxiliar: O (2 N )
Publicación traducida automáticamente
Artículo escrito por rahulrawat09 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA