Partición de un conjunto en K subconjuntos con igual suma

Dada una array de enteros de N elementos, la tarea es dividir esta array en K subconjuntos no vacíos de modo que la suma de los elementos en cada subconjunto sea la misma. Todos los elementos de esta array deben ser parte de exactamente una partición. 
Ejemplos: 
 

Input : arr = [2, 1, 4, 5, 6], K = 3
Output : Yes
we can divide above array into 3 parts with equal
sum as [[2, 4], [1, 5], [6]]

Input  : arr = [2, 1, 5, 5, 6], K = 3
Output : No
It is not possible to divide above array into 3
parts with equal sum

Podemos resolver este problema de forma recursiva, mantenemos una array para la suma de cada partición y una array booleana para verificar si un elemento ya está incluido en alguna partición o no. 
Primero, debemos verificar algunos casos base, 
si K es 1, entonces ya tenemos nuestra respuesta, la array completa solo es un subconjunto con la misma suma. 
Si N < K, entonces no es posible dividir el arreglo en subconjuntos con igual suma, porque no podemos dividir el arreglo en más de N partes. 
Si la suma de la array no es divisible por K, entonces no es posible dividir la array. Procederemos solo si k divide suma. Nuestro objetivo se reduce a dividir la array en K partes donde la suma de cada parte debe ser array_sum/K 
En el siguiente código, se escribe un método recursivo que intenta agregar un elemento de array en algún subconjunto. Si la suma de este subconjunto alcanza la suma requerida, iteramos recursivamente para la siguiente parte; de ​​lo contrario, retrocedemos para un conjunto diferente de elementos. Si el número de subconjuntos cuya suma alcanza la suma requerida es (K-1), indicamos que es posible dividir la array en K partes con la misma suma, porque los elementos restantes ya tienen una suma igual a la suma requerida. 
 

C++

// C++ program to check whether an array can be
// partitioned into K subsets of equal sum
#include <bits/stdc++.h>
using namespace std;
 
// Recursive Utility method to check K equal sum
// subsetition of array
/**
    array           - given input array
    subsetSum array   - sum to store each subset of the array
    taken           - boolean array to check whether element
                      is taken into sum partition or not
    K               - number of partitions needed
    N               - total number of element in array
    curIdx          - current subsetSum index
    limitIdx        - lastIdx from where array element should
                      be taken */
bool isKPartitionPossibleRec(int arr[], int subsetSum[], bool taken[],
                   int subset, int K, int N, int curIdx, int limitIdx)
{
    if (subsetSum[curIdx] == subset)
    {
        /*  current index (K - 2) represents (K - 1) subsets of equal
            sum last partition will already remain with sum 'subset'*/
        if (curIdx == K - 2)
            return true;
 
        //  recursive call for next subsetition
        return isKPartitionPossibleRec(arr, subsetSum, taken, subset,
                                            K, N, curIdx + 1, N - 1);
    }
 
    //  start from limitIdx and include elements into current partition
    for (int i = limitIdx; i >= 0; i--)
    {
        //  if already taken, continue
        if (taken[i])
            continue;
        int tmp = subsetSum[curIdx] + arr[i];
 
        // if temp is less than subset then only include the element
        // and call recursively
        if (tmp <= subset)
        {
            //  mark the element and include into current partition sum
            taken[i] = true;
            subsetSum[curIdx] += arr[i];
            bool nxt = isKPartitionPossibleRec(arr, subsetSum, taken,
                                            subset, K, N, curIdx, i - 1);
 
            // after recursive call unmark the element and remove from
            // subsetition sum
            taken[i] = false;
            subsetSum[curIdx] -= arr[i];
            if (nxt)
                return true;
        }
    }
    return false;
}
 
//  Method returns true if arr can be partitioned into K subsets
// with equal sum
bool isKPartitionPossible(int arr[], int N, int K)
{
    //  If K is 1, then complete array will be our answer
    if (K == 1)
        return true;
 
    //  If total number of partitions are more than N, then
    // division is not possible
    if (N < K)
        return false;
 
    // if array sum is not divisible by K then we can't divide
    // array into K partitions
    int sum = 0;
    for (int i = 0; i < N; i++)
        sum += arr[i];
    if (sum % K != 0)
        return false;
 
    //  the sum of each subset should be subset (= sum / K)
    int subset = sum / K;
    int subsetSum[K];
    bool taken[N];
 
    //  Initialize sum of each subset from 0
    for (int i = 0; i < K; i++)
        subsetSum[i] = 0;
 
    //  mark all elements as not taken
    for (int i = 0; i < N; i++)
        taken[i] = false;
 
    // initialize first subset sum as last element of
    // array and mark that as taken
    subsetSum[0] = arr[N - 1];
    taken[N - 1] = true;
 
    //  call recursive method to check K-substitution condition
    return isKPartitionPossibleRec(arr, subsetSum, taken,
                                     subset, K, N, 0, N - 1);
}
 
//  Driver code to test above methods
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 sum is possible.\n";
    else
        cout << "Partitions into equal sum is not possible.\n";
}

Java

// Java program to check whether an array can be
// partitioned into K subsets of equal sum
class GFG
{
 
// Recursive Utility method to check K equal sum
// subsetition of array
/**
    array         - given input array
    subsetSum array - sum to store each subset of the array
    taken         - boolean array to check whether element
                    is taken into sum partition or not
    K             - number of partitions needed
    N             - total number of element in array
    curIdx         - current subsetSum index
    limitIdx     - lastIdx from where array element should
                    be taken */
static boolean isKPartitionPossibleRec(int arr[], int subsetSum[], boolean taken[],
                int subset, int K, int N, int curIdx, int limitIdx)
{
    if (subsetSum[curIdx] == subset)
    {
        /* current index (K - 2) represents (K - 1) subsets of equal
            sum last partition will already remain with sum 'subset'*/
        if (curIdx == K - 2)
            return true;
 
        // recursive call for next subsetition
        return isKPartitionPossibleRec(arr, subsetSum, taken, subset,
                                            K, N, curIdx + 1, N - 1);
    }
 
    // start from limitIdx and include elements into current partition
    for (int i = limitIdx; i >= 0; i--)
    {
        // if already taken, continue
        if (taken[i])
            continue;
        int tmp = subsetSum[curIdx] + arr[i];
 
        // if temp is less than subset then only include the element
        // and call recursively
        if (tmp <= subset)
        {
            // mark the element and include into current partition sum
            taken[i] = true;
            subsetSum[curIdx] += arr[i];
            boolean nxt = isKPartitionPossibleRec(arr, subsetSum, taken,
                                            subset, K, N, curIdx, i - 1);
 
            // after recursive call unmark the element and remove from
            // subsetition sum
            taken[i] = false;
            subsetSum[curIdx] -= arr[i];
            if (nxt)
                return true;
        }
    }
    return false;
}
 
// Method returns true if arr can be partitioned into K subsets
// with equal sum
static boolean isKPartitionPossible(int arr[], int N, int K)
{
    // If K is 1, then complete array will be our answer
    if (K == 1)
        return true;
 
    // If total number of partitions are more than N, then
    // division is not possible
    if (N < K)
        return false;
 
    // if array sum is not divisible by K then we can't divide
    // array into K partitions
    int sum = 0;
    for (int i = 0; i < N; i++)
        sum += arr[i];
    if (sum % K != 0)
        return false;
 
    // the sum of each subset should be subset (= sum / K)
    int subset = sum / K;
    int []subsetSum = new int[K];
    boolean []taken = new boolean[N];
 
    // Initialize sum of each subset from 0
    for (int i = 0; i < K; i++)
        subsetSum[i] = 0;
 
    // mark all elements as not taken
    for (int i = 0; i < N; i++)
        taken[i] = false;
 
    // initialize first subset sum as last element of
    // array and mark that as taken
    subsetSum[0] = arr[N - 1];
    taken[N - 1] = true;
 
    // call recursive method to check K-substitution condition
    return isKPartitionPossibleRec(arr, subsetSum, taken,
                                    subset, K, N, 0, N - 1);
}
 
// 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.println("Partitions into equal sum is possible.");
    else
        System.out.println("Partitions into equal sum is not possible.");
}
}
 
// This code is contributed by Princi Singh

Python3

# Python3 program to check whether an array can be
# partitioned into K subsets of equal sum
 
# Recursive Utility method to check K equal sum
# subsetition of array
 
"""*
array     - given input array
subsetSum array - sum to store each subset of the array
taken     -boolean array to check whether element
is taken into sum partition or not
K         - number of partitions needed
N         - total number of element in array
curIdx     - current subsetSum index
limitIdx     - lastIdx from where array element should
be taken """
 
def isKPartitionPossibleRec(arr, subsetSum, taken,
                            subset, K, N, curIdx, limitIdx):
    if subsetSum[curIdx] == subset:
         
        """ current index (K - 2) represents (K - 1)
        subsets of equal sum last partition will
        already remain with sum 'subset'"""
        if (curIdx == K - 2):
            return True
         
        # recursive call for next subsetition
        return isKPartitionPossibleRec(arr, subsetSum, taken,
                                       subset, K, N, curIdx + 1 , N - 1)
     
    # start from limitIdx and include
    # elements into current partition
    for i in range(limitIdx, -1, -1):
         
        # if already taken, continue
        if (taken[i]):
            continue
        tmp = subsetSum[curIdx] + arr[i]
         
        # if temp is less than subset, then only
        # include the element and call recursively
        if (tmp <= subset):
             
            # mark the element and include into
            # current partition sum
            taken[i] = True
            subsetSum[curIdx] += arr[i]
            nxt = isKPartitionPossibleRec(arr, subsetSum, taken,
                                          subset, K, N, curIdx, i - 1)
                                           
            # after recursive call unmark the element and
            # remove from subsetition sum
            taken[i] = False
            subsetSum[curIdx] -= arr[i]
            if (nxt):
                return True
    return False
 
# Method returns True if arr can be
# partitioned into K subsets with equal sum
def isKPartitionPossible(arr, N, K):
     
    # If K is 1,
    # then complete array will be our answer
    if (K == 1):
        return True
     
    # If total number of partitions are more than N,
    # then division is not possible
    if (N < K):
        return False
         
    # if array sum is not divisible by K then
    # we can't divide array into K partitions
    sum = 0
    for i in range(N):
        sum += arr[i]
    if (sum % K != 0):
        return False
     
    # the sum of each subset should be subset (= sum / K)
    subset = sum // K
    subsetSum = [0] * K
    taken = [0] * N
     
    # Initialize sum of each subset from 0
    for i in range(K):
        subsetSum[i] = 0
         
    # mark all elements as not taken
    for i in range(N):
        taken[i] = False
         
    # initialize first subset sum as 
    # last element of array and mark that as taken
    subsetSum[0] = arr[N - 1]
    taken[N - 1] = True
     
    # call recursive method to check
    # K-substitution condition
    return isKPartitionPossibleRec(arr, subsetSum, taken,
                                   subset, K, N, 0, N - 1)
     
# Driver Code
arr = [2, 1, 4, 5, 3, 3 ]
N = len(arr)
K = 3
if (isKPartitionPossible(arr, N, K)):
    print("Partitions into equal sum is possible.\n")
else:
    print("Partitions into equal sum is not possible.\n")
 
# This code is contributed by SHUBHAMSINGH8410

C#

// C# program to check whether an array can be
// partitioned into K subsets of equal sum
using System;
 
class GFG
{
     
// Recursive Utility method to check K equal sum
// subsetition of array
/**
    array     - given input array
    subsetSum array - sum to store each subset of the array
    taken     - boolean array to check whether element
                    is taken into sum partition or not
    K         - number of partitions needed
    N         - total number of element in array
    curIdx     - current subsetSum index
    limitIdx     - lastIdx from where array element should
                    be taken */
static bool isKPartitionPossibleRec(int []arr, int []subsetSum, bool []taken,
                int subset, int K, int N, int curIdx, int limitIdx)
{
    if (subsetSum[curIdx] == subset)
    {
        /* current index (K - 2) represents (K - 1) subsets of equal
            sum last partition will already remain with sum 'subset'*/
        if (curIdx == K - 2)
            return true;
 
        // recursive call for next subsetition
        return isKPartitionPossibleRec(arr, subsetSum, taken, subset,
                                            K, N, curIdx + 1, N - 1);
    }
 
    // start from limitIdx and include elements into current partition
    for (int i = limitIdx; i >= 0; i--)
    {
        // if already taken, continue
        if (taken[i])
            continue;
        int tmp = subsetSum[curIdx] + arr[i];
 
        // if temp is less than subset then only include the element
        // and call recursively
        if (tmp <= subset)
        {
            // mark the element and include into current partition sum
            taken[i] = true;
            subsetSum[curIdx] += arr[i];
            bool nxt = isKPartitionPossibleRec(arr, subsetSum, taken,
                                            subset, K, N, curIdx, i - 1);
 
            // after recursive call unmark the element and remove from
            // subsetition sum
            taken[i] = false;
            subsetSum[curIdx] -= arr[i];
            if (nxt)
                return true;
        }
    }
    return false;
}
 
// Method returns true if arr can be partitioned into K subsets
// with equal sum
static bool isKPartitionPossible(int []arr, int N, int K)
{
    // If K is 1, then complete array will be our answer
    if (K == 1)
        return true;
 
    // If total number of partitions are more than N, then
    // division is not possible
    if (N < K)
        return false;
 
    // if array sum is not divisible by K then we can't divide
    // array into K partitions
    int sum = 0;
    for (int i = 0; i < N; i++)
        sum += arr[i];
    if (sum % K != 0)
        return false;
 
    // the sum of each subset should be subset (= sum / K)
    int subset = sum / K;
    int []subsetSum = new int[K];
    bool []taken = new bool[N];
 
    // Initialize sum of each subset from 0
    for (int i = 0; i < K; i++)
        subsetSum[i] = 0;
 
    // mark all elements as not taken
    for (int i = 0; i < N; i++)
        taken[i] = false;
 
    // initialize first subset sum as last element of
    // array and mark that as taken
    subsetSum[0] = arr[N - 1];
    taken[N - 1] = true;
 
    // call recursive method to check K-substitution condition
    return isKPartitionPossibleRec(arr, subsetSum, taken,
                                    subset, K, N, 0, N - 1);
}
 
// Driver code
static public void Main ()
{
     
    int []arr = {2, 1, 4, 5, 3, 3};
    int N = arr.Length;
    int K = 3;
 
    if (isKPartitionPossible(arr, N, K))
        Console.WriteLine("Partitions into equal sum is possible.");
    else
        Console.WriteLine("Partitions into equal sum is not possible.");
}
}
 
// This code is contributed by ajit.

Javascript

<script>
// Javascript program to check whether an array can be
// partitioned into K subsets of equal sum
 
 
// Recursive Utility method to check K equal sum
// subsetition of array
/**
    array           - given input array
    subsetSum array   - sum to store each subset of the array
    taken           - boolean array to check whether element
                      is taken into sum partition or not
    K               - number of partitions needed
    N               - total number of element in array
    curIdx          - current subsetSum index
    limitIdx        - lastIdx from where array element should
                      be taken */
function isKPartitionPossibleRec(arr, subsetSum, taken, subset, K, N, curIdx, limitIdx) {
    if (subsetSum[curIdx] == subset) {
        /*  current index (K - 2) represents (K - 1) subsets of equal
            sum last partition will already remain with sum 'subset'*/
        if (curIdx == K - 2)
            return true;
 
        //  recursive call for next subsetition
        return isKPartitionPossibleRec(arr, subsetSum, taken, subset,
            K, N, curIdx + 1, N - 1);
    }
 
    //  start from limitIdx and include elements into current partition
    for (let i = limitIdx; i >= 0; i--) {
        //  if already taken, continue
        if (taken[i])
            continue;
        let tmp = subsetSum[curIdx] + arr[i];
 
        // if temp is less than subset then only include the element
        // and call recursively
        if (tmp <= subset) {
            //  mark the element and include into current partition sum
            taken[i] = true;
            subsetSum[curIdx] += arr[i];
            let nxt = isKPartitionPossibleRec(arr, subsetSum, taken,
                subset, K, N, curIdx, i - 1);
 
            // after recursive call unmark the element and remove from
            // subsetition sum
            taken[i] = false;
            subsetSum[curIdx] -= arr[i];
            if (nxt)
                return true;
        }
    }
    return false;
}
 
//  Method returns true if arr can be partitioned into K subsets
// with equal sum
function isKPartitionPossible(arr, N, K) {
    //  If K is 1, then complete array will be our answer
    if (K == 1)
        return true;
 
    //  If total number of partitions are more than N, then
    // division is not possible
    if (N < K)
        return false;
 
    // if array sum is not divisible by K then we can't divide
    // array into K partitions
    let sum = 0;
    for (let i = 0; i < N; i++)
        sum += arr[i];
    if (sum % K != 0)
        return false;
 
    //  the sum of each subset should be subset (= sum / K)
    let subset = sum / K;
    let subsetSum = new Array(K);
    let taken = new Array(N);
 
    //  Initialize sum of each subset from 0
    for (let i = 0; i < K; i++)
        subsetSum[i] = 0;
 
    //  mark all elements as not taken
    for (let i = 0; i < N; i++)
        taken[i] = false;
 
    // initialize first subset sum as last element of
    // array and mark that as taken
    subsetSum[0] = arr[N - 1];
    taken[N - 1] = true;
 
    //  call recursive method to check K-substitution condition
    return isKPartitionPossibleRec(arr, subsetSum, taken,
        subset, K, N, 0, N - 1);
}
 
//  Driver code to test above methods
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 sum is possible");
else
    document.write("Partitions into equal sum is not possible")
     
    // This code is contributed by saurabh_jaiswal.
</script>

Producción: 
 

Partitions into equal sum is possible.

Análisis de Complejidad: 

Complejidad temporal: O(2^(N * K)). 
Porque si tenemos K árboles apilados uno encima del otro, la nueva altura del árbol es K * es decir, un subconjunto no es independiente del otro.
Complejidad espacial: O(N). 
Se requiere espacio adicional para la array visitada.
Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *