Recuento de subconjuntos que se pueden dividir en dos conjuntos no vacíos con la misma suma

Dada una array Arr[] de tamaño N , la tarea es encontrar el recuento de subconjuntos de Arr[] que se pueden dividir en dos grupos no vacíos que tengan la misma suma.

Ejemplos: 

Entrada: Arr[] = {2, 3, 4, 5}
Salida: 2
Explicación: Los subconjuntos son: 
{2, 3, 5} que se pueden dividir en {2, 3} y {5}
{2, 3, 4, 5} que se puede dividir en {2, 5} y {3, 4}

Entrada: Arr[] = {1, 2, 3, 4, 5}
Salida: 7

Enfoque ingenuo: el enfoque más simple es generar todos los subconjuntos y para cada subconjunto S , si tiene una suma de A , encuentre todos los subconjuntos de S y verifique si tiene una suma de A/2. 

Complejidad de Tiempo: O(4 ^N ) 
Espacio Auxiliar: O(1)

Enfoque eficiente: la idea para resolver el problema de manera eficiente es utilizar la técnica de encuentro en el medio . 

• Divida la array por igual en dos mitades y para cada mitad calcule todos los subconjuntos posibles.
• Para los elementos incluidos en un subconjunto en cualquiera de las mitades, asígnelo al primer grupo o al segundo grupo sumando o restando de la variable ‘ suma ‘ (la suma se inicializa en 0 ).
• Para la primera mitad de la array, si se asigna un elemento al primer grupo, simplemente agregue su valor a la suma, de lo contrario, réstelo. Para la segunda mitad de la array, si se asigna un elemento al primer grupo, réstelo de la suma, de lo contrario, agréguelo.

Siga los pasos a continuación para resolver el problema:

• Declare una array booleana global ‘canSplit’ de tamaño (1 << N) para almacenar el resultado de cada subconjunto si se puede dividir en dos grupos que tengan la misma suma.
• Declare un mapa global para asignar la suma de un subconjunto a una ID y para encontrar si ya existe un subconjunto con la misma suma que el subconjunto actual.
• Declare un Vector global de Vector para almacenar todas las máscaras de bits que tienen la misma suma juntas.
• Defina una función recursiva, digamos makeSubsets1(i, sum, mask) para construir todos los subconjuntos de la primera mitad de la array.
  • Caso base, si i == N/2 , entonces la primera mitad de la array se ha recorrido por completo.
    • Si la suma del subconjunto actual representado por la máscara de bits es diferente de los subconjuntos ya formados, incremente el ID de la variable en 1 y asigne el valor de sum a este ID .
    • Recuperar el número de identificación de la suma actual.
    • Agregue el subconjunto representado por la máscara de bits al vector de la ID recuperada.
  • El número en el índice actual puede ser:
    • Excluido del subconjunto actual.
    • Incluido al primer grupo del subconjunto. En este caso, sumamos el número a ‘ suma ‘.
    • Incluido en el segundo grupo del subconjunto. En este caso, restamos el número de ‘ suma ‘.
• Defina una función recursiva, digamos makeSubsets2(i, sum, mask) para construir todos los subconjuntos a partir de la segunda mitad de la array.
  • Caso base, si i == N , entonces toda la array se ha recorrido completamente comenzando desde el medio.
    • Si algún subconjunto en la primera mitad de la array tiene la misma suma que la del subconjunto actual, entonces el OR bit a bit de los dos forma un subconjunto válido ya que tienen el mismo valor de desequilibrio . En otras palabras si:
      • ∑(Primer grupo) ₁ – ∑(Segundo grupo) ₁  = ∑(Segundo grupo) ₂ – ∑(Primer grupo) ₂ , reordenando términos,
      • ∑(Primer grupo) ₁ + ∑(Primer grupo) ₂ = ∑(Segundo grupo) ₁ + ∑(Segundo grupo) ₂
    • Por lo tanto, el OR bit a bit de los dos subconjuntos se puede dividir en dos grupos que tienen sumas iguales . Iterar a través de todos los subconjuntos de la primera mitad que tengan la misma suma y marcar Bitwise OR con el subconjunto actual de la segunda mitad como ‘ verdadero ‘, lo que indica un subconjunto válido.
  • El número en el índice actual puede ser:
    • Excluido del subconjunto actual.
    • Incluido en el segundo grupo del subconjunto. En este caso, sumamos el número a ‘ suma ‘.
    • Incluido al primer grupo del subconjunto. En este caso, restamos el número de ‘ suma ‘.
• Repita todos los subconjuntos y aumente la respuesta en 1 si canSplit[mask] = true .
• Imprime la respuesta.

A continuación se muestra el código para el enfoque anterior:

// C++ program for the above approach.
 
#include <bits/stdc++.h>
using namespace std;
 
// Boolean array to check if elements
// represented by a bitmask(subset)
// can be split into two non-empty groups
// having equal sum.
bool canSplit[1 << 20];
 
// Map to store sum of subsets
// and find if there is a subset
// with the current sum.
map<int, int> mp;
 
// Vector of vector to store
// all the bitmasks having the
// same sum together.
vector<vector<int> > subsets(1 << 20);
 
// Variable to count subsets
// having unique sums.
int ID;
 
// Function to generate all possible
// subsets from first half
// of the array.
void makeSubsets1(int i, int N, int sum,
                  int mask, int Arr[])
{
 
    // If first half of the array
    // is traversed.
    if (i == N) {
 
        // If none of the previously formed
        // subsets have the same sum
        // as the current subset.
        if (mp.find(sum) == mp.end()) {
 
            // Increase ID by 1 as the
            // subsets having a unique
            // sum value has increased by 1.
            ++ID;
 
            // Assign the value of sum to ID.
            mp[sum] = ID;
        }
 
        // Retrieve the subset number
        // having this sum.
        int id = mp[sum];
 
        // Add the bitmask to the vector
        // of this particular subset id.
        subsets[id].push_back(mask);
        return;
    }
 
    // Exclude the current element
    // from the subset
    makeSubsets1(i + 1, N, sum,
                 mask, Arr);
 
    // Include the current element
    // to the first group of the subset.
    makeSubsets1(i + 1, N, sum + Arr[i],
                 mask | (1 << i), Arr);
 
    // Include the current element
    // to the second group of the subset.
    makeSubsets1(i + 1, N, sum - Arr[i], mask | (1 << i),
                 Arr);
}
 
// Function to generate all possible
// subsets from second half of array.
void makeSubsets2(int i, int N, int sum,
                  int mask, int Arr[])
{
 
    // If the second half
    // of the array is traversed.
    if (i == N) {
 
        // If the current subset sum has
        // occurred before in the
        // first part of the array, then the
        // combined subset from both halves
        // of the array forms a valid subset
        if (mp.find(sum) != mp.end()) {
 
            // Iterate through all the bitmasks
            // from the first part of the array
            // having the same current sum.
            for (auto num : subsets[mp[sum]]) {
 
                // Mark the bitwise OR
                // of both subsets as TRUE.
                canSplit[num | mask] = 1;
            }
        }
        return;
    }
 
    // Exclude the current element
    // from the subset.
    makeSubsets2(i + 1, N, sum, mask, Arr);
 
    // Include the current element
    // to the second group of the subset.
    makeSubsets2(i + 1, N, sum + Arr[i], mask | (1 << i),
                 Arr);
 
    // Include the current element
    // to the first group of the subset.
    makeSubsets2(i + 1, N, sum - Arr[i], mask | (1 << i),
                 Arr);
}
 
// Utility function to find all subsets from both halves of
// the array.
int UtilCountOfSubsets(int N, int Arr[])
{
    // Split the array into two parts.
    int mid = N / 2;
 
    // Function calls
    makeSubsets1(0, mid, 0, 0, Arr);
    makeSubsets2(mid, N, 0, 0, Arr);
 
    int ans = 0;
 
    // Iterate through all bitmasks
    // from 1 to 2^N - 1.
    for (int i = 1; i < (1 << N); ++i) {
 
        // If canSplit[i] is true,
        // increase the answer by 1.
        ans += canSplit[i];
    }
 
    // Return the answer.
    return ans;
}
 
// Driver code
int main()
{
 
    // Input Array
    int Arr[] = { 2, 3, 4, 5 };
 
    // Size of array
    int N = sizeof(Arr) / sizeof(Arr[0]);
 
    cout << UtilCountOfSubsets(N, Arr) << endl;
}

import java.util.*;
import java.io.*;
 
// Java program for the above approach
class GFG{
 
  // Boolean array to check if elements
  // represented by a bitmask(subset)
  // can be split into two non-empty groups
  // having equal sum.
  public static Boolean canSplit[] = new Boolean[1 << 20];
 
  // Map to store sum of subsets
  // and find if there is a subset
  // with the current sum.
  public static TreeMap<Integer, Integer> mp = new TreeMap<Integer, Integer>();
 
  // Vector of vector to store
  // all the bitmasks having the
  // same sum together.
  public static ArrayList<ArrayList<Integer>> subsets = new ArrayList<ArrayList<Integer>>();
 
  // Variable to count subsets
  // having unique sums.
  public static int ID;
 
  // Function to generate all possible
  // subsets from first half
  // of the array.
  public static void makeSubsets1(int i, int N, int sum, int mask, int Arr[])
  {
 
    // If first half of the array
    // is traversed.
    if (i == N) {
 
      // If none of the previously formed
      // subsets have the same sum
      // as the current subset.
      if (!mp.containsKey(sum)) {
 
        // Increase ID by 1 as the
        // subsets having a unique
        // sum value has increased by 1.
        ++ID;
 
        // Assign the value of sum to ID.
        mp.put(sum, ID);
      }
 
      // Retrieve the subset number
      // having this sum.
      int id = mp.get(sum);
 
      // Add the bitmask to the vector
      // of this particular subset id.
      subsets.get(id).add(mask);
      return;
    }
 
    // Exclude the current element
    // from the subset
    makeSubsets1(i + 1, N, sum, mask, Arr);
 
    // Include the current element
    // to the first group of the subset.
    makeSubsets1(i + 1, N, sum + Arr[i], mask | (1 << i), Arr);
 
    // Include the current element
    // to the second group of the subset.
    makeSubsets1(i + 1, N, sum - Arr[i], mask | (1 << i), Arr);
  }
 
  // Function to generate all possible
  // subsets from second half of array.
  public static void makeSubsets2(int i, int N, int sum, int mask, int Arr[])
  {
 
    // If the second half
    // of the array is traversed.
    if (i == N) {
 
      // If the current subset sum has
      // occurred before in the
      // first part of the array, then the
      // combined subset from both halves
      // of the array forms a valid subset
      if (mp.containsKey(sum)) {
 
        // Iterate through all the bitmasks
        // from the first part of the array
        // having the same current sum.
        for(Integer num : subsets.get(mp.get(sum))) {
 
          // Mark the bitwise OR
          // of both subsets as TRUE.
          canSplit[num | mask] = true;
        }
      }
      return;
    }
 
    // Exclude the current element
    // from the subset.
    makeSubsets2(i + 1, N, sum, mask, Arr);
 
    // Include the current element
    // to the second group of the subset.
    makeSubsets2(i + 1, N, sum + Arr[i], mask | (1 << i), Arr);
 
    // Include the current element
    // to the first group of the subset.
    makeSubsets2(i + 1, N, sum - Arr[i], mask | (1 << i), Arr);
  }
 
  // Utility function to find all subsets from both halves of
  // the array.
  public static int UtilCountOfSubsets(int N, int Arr[])
  {
    // Split the array into two parts.
    int mid = N / 2;
 
    // Function calls
    makeSubsets1(0, mid, 0, 0, Arr);
    makeSubsets2(mid, N, 0, 0, Arr);
 
    int ans = 0;
 
    // Iterate through all bitmasks
    // from 1 to 2^N - 1.
    for (int i = 1 ; i < (1 << N) ; ++i) {
 
      // If canSplit[i] is true,
      // increase the answer by 1.
      if(canSplit[i]){
        ans++;
      }
    }
 
    // Return the answer.
    return ans;
  }
 
  // Driver code
  public static void main(String args[])
  {
    int Arr[] = {2, 3, 4, 5};
    int N = Arr.length;
    for(int i = 0 ; i < (1<<20) ; i++){
      subsets.add(new ArrayList<Integer>());
      canSplit[i] = false;
    }
 
    System.out.println(UtilCountOfSubsets(N, Arr));
  }
}
 
// This code is contributed by subhamgoyal2014.

# python3 program for the above approach.
 
# Boolean array to check if elements
# represented by a bitmask(subset)
# can be split into two non-empty groups
# having equal sum.
canSplit = [0 for _ in range(1 << 20)]
 
# Map to store sum of subsets
# and find if there is a subset
# with the current sum.
mp = {}
 
# Vector of vector to store
# all the bitmasks having the
# same sum together.
subsets = [[] for _ in range(1 << 20)]
 
# Variable to count subsets
# having unique sums.
ID = 0
 
# Function to generate all possible
# subsets from first half
# of the array.
 
 
def makeSubsets1(i, N, sum, mask, Arr):
    global canSplit, mp, subsets, ID
 
    # If first half of the array
    # is traversed.
    if (i == N):
 
                # If none of the previously formed
                # subsets have the same sum
                # as the current subset.
        if (not sum in mp):
 
                        # Increase ID by 1 as the
                        # subsets having a unique
                        # sum value has increased by 1.
            ID += 1
 
            # Assign the value of sum to ID.
            mp[sum] = ID
 
            # Retrieve the subset number
            # having this sum.
        id = mp[sum]
 
        # Add the bitmask to the vector
        # of this particular subset id.
        subsets[id].append(mask)
        return
 
        # Exclude the current element
        # from the subset
    makeSubsets1(i + 1, N, sum, mask, Arr)
 
    # Include the current element
    # to the first group of the subset.
    makeSubsets1(i + 1, N, sum + Arr[i], mask | (1 << i), Arr)
 
    # Include the current element
    # to the second group of the subset.
    makeSubsets1(i + 1, N, sum - Arr[i], mask | (1 << i), Arr)
 
 
# Function to generate all possible
# subsets from second half of array.
def makeSubsets2(i, N, sum, mask, Arr):
    global canSplit, mp, subsets, ID
 
    # If the second half
    # of the array is traversed.
    if (i == N):
 
                # If the current subset sum has
                # occurred before in the
                # first part of the array, then the
                # combined subset from both halves
                # of the array forms a valid subset
        if (sum in mp):
 
                        # Iterate through all the bitmasks
                        # from the first part of the array
                        # having the same current sum.
            for num in subsets[mp[sum]]:
 
                                # Mark the bitwise OR
                                # of both subsets as TRUE.
                canSplit[num | mask] = 1
        return
 
        # Exclude the current element
        # from the subset.
    makeSubsets2(i + 1, N, sum, mask, Arr)
 
    # Include the current element
    # to the second group of the subset.
    makeSubsets2(i + 1, N, sum + Arr[i], mask | (1 << i),
                 Arr)
 
    # Include the current element
    # to the first group of the subset.
    makeSubsets2(i + 1, N, sum - Arr[i], mask | (1 << i),
                 Arr)
 
 
# Utility function to find all subsets from both halves of
# the array.
def UtilCountOfSubsets(N, Arr):
    global canSplit, mp, subsets, ID
    # Split the array into two parts.
    mid = N // 2
 
    # Function calls
    makeSubsets1(0, mid, 0, 0, Arr)
    makeSubsets2(mid, N, 0, 0, Arr)
 
    ans = 0
 
    # Iterate through all bitmasks
    # from 1 to 2^N - 1.
    for i in range(1, 1 << N):
 
                # If canSplit[i] is true,
                # increase the answer by 1.
        ans += canSplit[i]
 
        # Return the answer.
    return ans
 
 
# Driver code
if __name__ == "__main__":
 
        # Input Array
    Arr = [2, 3, 4, 5]
 
    # Size of array
    N = len(Arr)
 
    print(UtilCountOfSubsets(N, Arr))
 
    # This code is contributed by rakeshsahni

2

Complejidad temporal: O(6 ^N/2 ) . 

• La generación de todos los subconjuntos a partir de la primera y la segunda mitad de la array requiere O(3 ^N/2 ).
• En el peor de los casos, todos los subconjuntos de la primera mitad pueden coincidir con el subconjunto actual de la segunda mitad tomando O(2 ^N/2 ).
• Por lo tanto, la complejidad del tiempo total es O(3 ^N/2 * 2 ^N/2 ) = O(6 ^N/2 ).

Espacio Auxiliar: O(2 ^N )