Subconjuntos que tienen Suma entre A y B

Dado un conjunto de N enteros. Encuentre cuántos subconjuntos de una array dada tienen una suma entre A y B (inclusive). 
 

Restricciones: 
1 ≤ N ≤ 34, 
-2 * 10 ⁷ ≤ arr _i ≤ 2 * 10 ⁷ 
-5 * 10 ⁸ ≤ A, B ≤ 5 * 10 ⁸ 
 

Ejemplos: 
 

Input : S[] = { 1, -2, 3 }, A = -1, B = 2
Output : 5

Explanation:
1) 0 = 0 (the empty subset)
2) {1} = 1
3) {1, -2} = 1 + (-2) = -1
4) {-2, 3} = (-2) + 3 = 1
5) {1, -2, 3} = 1 + (-2) + 3 = 2

Método 1 (Fuerza bruta) : podemos generar todos los subconjuntos de los números dados, es decir, Power Set y encontrar el número de subconjuntos que darían una suma entre A y B. Pero esto tendrá 2 ³⁴ operaciones como máximo, lo cual no es muy eficiente. Por lo tanto, a continuación se muestra un enfoque eficiente para resolver este problema.
Método 2 ( Meet In The Middle ) : Esto básicamente reduce la complejidad del tiempo de O(2 ^N ) a O(2 ^N/2 ) 
Dividimos el conjunto en dos conjuntos [0…N/2] y [(N/2 + 1 )…(N-1)] y generar todas las sumas de los subconjuntos individualmente para los dos conjuntos que serán 2 * 2 ¹⁷operaciones. Ahora, lo que podemos hacer es encontrar las combinaciones de estos conjuntos que darían la suma deseada. Esto nuevamente se puede hacer de una manera eficiente, ordenar uno del conjunto resumido y buscar binariamente los valores que producirán la suma del valor particular del otro conjunto. Ordene el segundo conjunto y para cada elemento del primer conjunto, busque el límite inferior de A – S2[i] (digamos ‘bajo’) y el límite superior de B – S2[i] 
(digamos ‘alto’). Resta (alto – bajo) para obtener la respuesta deseada.
 

Por ejemplo , S = { 1, 2, -1, 0 }, A = 1, B = -1. 
Después de dividir S en dos conjuntos, S1 = { 1, 2 } y S2 = { -1, 0 }. 
Conjunto potencia de S1 = { {0}, {1}, {2}, {1, 2} } y Conjunto potencia de S2 = { {0}, {-1}, {0}, {-1, 0} } 
Subconjunto Suma de S1 = { 0, 1, 2, 3 } y Subconjunto Suma de S2 = { 0, -1, 0, -1 } 
Ahora ordene S2 { -1, -1, 0, 0 } y para cada valor en S1, buscamos valores binarios que producirían la suma deseada. Para 0 buscamos (-1) – 0 = -1 para el límite inferior y 1 – 0 = 1 para el límite superior en S2, para 1 buscamos (-1) – 1 = -2 y 1 – 1 = 0 en S2 y así sucesivamente. 
 

// C++ program to find the Number of Subsets that
// have sum between A and B
#include <bits/stdc++.h>
using namespace std;
 
/* Function to Generate all subsets of a set
   start --> Starting Index of the Set for the
             first/second half Set
   setSize --> Number of element in half Set
   S --> Original Complete Set
   res --> Store the subsets sums */
void generateSubsets(int start, int setSize, int S[],
                                    vector<int>& res)
{
    // setSize of power set of a set with setSize
    // N is (2^n - 1)
    unsigned int pow_setSize = pow(2, setSize);
 
    // Store the sum of particular subset of set
    int sum;
 
    // Run from counter 000..0 to 111..1
    for (int counter = 0; counter < pow_setSize; counter++) {
 
        // set the sum initially to zero
        sum = 0;
 
        for (int j = 0; j < setSize; j++) {
 
            // Check if jth bit in the counter is set
            // If set then print jth element from set
            if (counter & (1 << j))
                sum += S[j + start];
        }
 
        // Store the sum in a vector
        res.push_back(sum);
    }
}
 
int numberOfSubsets(int S[], int N, int A, int B)
{
    // Vectors to store the subsets sums
    // of two half sets individually
    vector<int> S1, S2;
 
    // Generate subset sums for the first half set
    generateSubsets(0, N / 2, S, S1);
 
    // Generate subset sums for the second half set
    if (N % 2 != 0)
        generateSubsets(N / 2, N / 2 + 1, S, S2);
    else
        generateSubsets(N / 2, N / 2, S, S2);
 
    // Sort the second half set
    sort(S2.begin(), S2.end());
 
    // Vector Iterator for S1 and S2;
    vector<int>::iterator low, high;
 
    // number of required subsets with desired Sum
    int ans = 0;
 
    for (int i = 0; i < S1.size(); i++) {
 
        // search for lower bound
        low = lower_bound(S2.begin(), S2.end(), A - S1[i]);
 
        // search for upper bound
        high = upper_bound(S2.begin(), S2.end(), B - S1[i]);
 
        // Add up to get the desired answer
        ans += (high - low);
    }
    return ans;
}
 
// Driver Program to test above functions
int main()
{
    int S[] = { 1, -2, 3 };
    int N = sizeof(S) / sizeof(S[0]);
 
    int A = -1, B = 2;
 
    // Find the number of subsets with desired Sum
    cout << numberOfSubsets(S, N, A, B) << endl;
    return 0;
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.function.BiPredicate;
 
// Java program to find the Number of Subsets that
// have sum between A and B
public class Main
{
   
    /* Function to Generate all subsets of a set
    start --> Starting Index of the Set for the
             first/second half Set
    setSize --> Number of element in half Set
    S --> Original Complete Set
    res --> Store the subsets sums */
    private static void generateSubsetSumsRecur(int[] arr, int st, int end, int index, int runningSum, List<Integer> sums) {
        if (index == end+1) {
            sums.add(runningSum);
            return;
        }
        generateSubsetSumsRecur(arr, st, end, index+1, runningSum+arr[index], sums);
        generateSubsetSumsRecur(arr, st, end, index+1, runningSum, sums);
    }
    private static long numberOfSubsets(int arr[],int n, int a, int b) {
        // Generate subset sums for the first half set
        List<Integer> sums = new ArrayList<>();
        generateSubsetSumsRecur(arr, 0, n/2, 0, 0, sums);
        Integer[] firstSubsetSums= sums.toArray(new Integer[0]);
     
        // Generate subset sums for the second half set
        List<Integer> sums2 = new ArrayList<>();
        generateSubsetSumsRecur(arr, n/2+1, n-1, n/2+1, 0, sums2);
        Integer[] secondSubsetSums= sums2.toArray(new Integer[0]);
         
        // Sort the second half set
        Arrays.sort(secondSubsetSums);
         
        long count = 0;
        for(int i=0; i<firstSubsetSums.length; i++) {
            int p = findLastIdxWithFalsePredicate(secondSubsetSums,
                                                  a-firstSubsetSums[i],
                                                  (sum, mark)->sum>=mark);
            int q = findLastIdxWithFalsePredicate(secondSubsetSums,
                                                  b-firstSubsetSums[i],
                                                  (sum, mark)->sum>mark);
            count += (q-p);
        }
        return count;
    }
    private static int findLastIdxWithFalsePredicate(Integer[] sums,
                                                     int val,
                                                     BiPredicate<Integer, Integer> pred) {
        int min = 0;
        int max = sums.length-1;
        while (min<max) {
            int mid = min + (max-min+1)/2;
            if (pred.test(sums[mid], val)) {
                max = mid-1;
            } else {
                min = mid;
            }
        }
        if (pred.test(sums[min], val))
            return -1;
        return min;
    }
   
  // Driver code
    public static void main(String args[])
    {
        int N = 3;
        int A = -1;
        int B = 2;
         
        int arr[] = { 1, -2, 3 };
        System.out.println(numberOfSubsets(arr, N, A, B));
    }
}
 
// This code is contributed by Manu Pathria

# Python3 program to find the number of
# subsets that have sum between A and B
 
# Module for Bisection algorithms
import bisect
 
'''
Function to Generate all subsets of a set
    start --> Starting Index of the Set for the
        first/second half Set
    setSize --> Number of element in half Set
    S --> Original Complete Set
    res --> Store the subsets sums
'''
def generateSubsets(start, setSize, S, res):
     
    # setSize of power set of a set with setSize
    # N is (2^n - 1)
    pow_setSize = pow(2, setSize)
 
    # Store the sum of particular subset of set
    add = 0
 
    # Run from counter 000..0 to 111..1
    for counter in range(pow_setSize):
         
        # set the sum initially to zero
        add = 0
 
        for j in range(setSize):
             
            # Check if jth bit in the counter is set
            # If set then print jth element from set
            if counter & (1 << j):
                add += S[j + start]
 
        # Store the sum in a vector
        res.append(add)
         
def numberOfSubsets(S, N, A, B):
 
    # Vectors to store the subsets sums
    # of two half sets individually
    S1 = []
    S2 = []
 
    # Generate subset sums for the first half set
    generateSubsets(0, N // 2, S, S1)
 
    # Generate subset sums for the second half set
    if (N % 2 != 0):
        generateSubsets(N // 2,
                        N // 2 + 1, S, S2)
    else:
        generateSubsets(N // 2,
                        N // 2, S, S2)
 
    # Sort the second half set
    S2.sort()
 
    # Number of required subsets
    # with desired Sum
    ans = 0
 
    for i in range(len(S1)):
 
        # Search for lower bound
        low = bisect.bisect_left(S2, A - S1[i])
 
        # Search for upper bound
        high = bisect.bisect_right(S2, B - S1[i])
 
        # Add up to get the desired answer
        ans += (high - low)
 
    return ans
 
# Driver code
if __name__=="__main__":
 
    S = [ 1, -2, 3 ]
    N = len(S)
 
    A = -1
    B = 2
 
    # Find the number of subsets
    # with desired Sum
    print(numberOfSubsets(S, N, A, B))
     
# This code is contributed by vinaylingam

5

Complejidad temporal: O(2 * 2 ^N/2 ), donde N es el tamaño del conjunto.