Consultas de suma de subconjuntos usando conjunto de bits

Dada una array arr[] y un número de consultas, donde en cada consulta tenemos que verificar si un subconjunto cuya suma es igual al número dado existe en la array o no. 

Ejemplos:

Input : arr[]   = {1, 2, 3};
        query[] = {5, 3, 8}  
Output : Yes, Yes, No
There is a subset with sum 5, subset is {2, 3}
There is a subset with sum 3, subset is {1, 2}
There is no subset with sum 8.

Input : arr[] = {4, 1, 5};
        query[] = {7, 9}
Output : No, Yes
There is no subset with sum 7.
There is a subset with sum 9, subset is {4, 5}

La idea es usar un contenedor de conjuntos de bits en C++ . Usando el conjunto de bits, podemos precalcular la existencia de todas las sumas de subconjuntos en una array en O (n) y responder consultas posteriores en solo O (1). Básicamente usamos una array de bits bit[] para representar la suma del subconjunto de elementos en la array. El tamaño de bit[] debe ser al menos la suma de todos los elementos de la array más 1 para responder a todas las consultas. Mantenemos bit[x] como 1 si x es una suma de subconjuntos de una array dada, de lo contrario, es falso. Tenga en cuenta que se supone que la indexación comienza con 0.

For every element arr[i] of input array,
we do following

// bit[x] will be 1 if x is a subset
// sum of arr[], else 0
bit = bit | (bit << arr[i])

¿Como funciona esto?

Let us consider arr[] = {3, 1, 5}, we need 
to whether a subset sum of x exists or not, 
where 0 ≤ x ≤ Σarri.

We create a bitset bit[10] and reset all the  
bits to 0, i.e., we make it 0000000000.

Set the 0th bit, because a subset sum of 0 
exists in every array.
Now, the bit array is 0000000001

Apply the above technique for all the elements
of the array :
Current bitset = 0000000001

After doing "bit = bit | (bit << 3)", 
bitset becomes    0000001001


After doing "bit | (bit << 1)", 
bitset becomes    0000011011


After doing "bit | (bit << 5)", 
bitset becomes    1101111011    

Finalmente, tenemos la array de bits como 1101111011, por lo que, si bit[x] es 1, entonces existe una suma de subconjuntos de x; de lo contrario, no existe. Podemos observar claramente que en el arreglo existe una suma de subconjuntos de todos los números del 0 al 9 excepto el 2 y el 7. 

Implementación:

// C++ program to answer subset sum queries using bitset
#include <bits/stdc++.h>
using namespace std;
 
// Maximum allowed query value
# define MAXSUM 10000
 
// function to check whether a subset sum equal to n
// exists in the array or not.
void processQueries(int query[], int nq, bitset<MAXSUM> bit)
{
 // One by one process subset sum queries
 for (int i=0; i<nq; i++)
 {
 int x = query[i];
 
 // If x is beyond size of bit[]
 if (x >= MAXSUM)
 {
  cout << "NA, ";
  continue;
 }
 
 // Else if x is a subset sum, then x'th bit
 // must be set
 bit[x]? cout << "Yes, " : cout << "No, ";
 }
}
 
// function to store all the subset sums in bit vector
void preprocess(bitset<MAXSUM> &bit, int arr[], int n)
{
 // set all the bits to 0
 bit.reset();
 
 // set the 0th bit because subset sum of 0 exists
 bit[0] = 1;
 
 // Process all array elements one by one
 for (int i = 0; i < n; ++i)
 
  // Do OR of following two
  // 1) All previous sums. We keep previous value
  // of bit.
  // 2) arr[i] added to every previous sum. We
  // move all previous indexes arr[i] ahead.
  bit |= (bit << arr[i]);
}
 
// Driver program
int main()
{
 int arr[] = {3, 1, 5};
 int query[] = {8, 7};
 
 int n = sizeof(arr) / sizeof(arr[0]);
 int nq = sizeof(query) / sizeof(query[0]);
 
 // a vector of MAXSUM number of bits
 bitset<MAXSUM> bit;
 
 preprocess(bit, arr, n);
 processQueries(query, nq, bit);
 
 return 0;
}

Yes, No, 

Complejidad de tiempo : O(n) para precálculo y O(1) para consultas subsiguientes, donde n es el número de elementos en la array.
Espacio Auxiliar: O(n)

Este artículo es una contribución de Avinash Kumar Saw . 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.