Subset Sum Queries in a Range using Bitset

0 0 6 minutes read

Given an array[] of N positive integers and M queries. Each query consists of two integers L and R represented by a range. For each query, find the count of numbers that lie in the given range which can be expressed as the sum of any subset of given array.

Prerequisite : Subset Sum Queries using Bitset

Examples:

Input : arr[] = { 1, 2, 2, 3, 5 }, M = 4 L = 1, R = 2 L = 1, R = 5 L = 3, R = 6 L = 9, R = 30
Output : 2 5 4 5
Explanation : For the first query, in range [1, 2] all numbers i.e. 1 and 2 can be expressed as a subset sum, 1 as 1, 2 as 2. For the second query, in range [1, 5] all numbers i.e. 1, 2, 3, 4 and 5 can be expressed as subset sum, 1 as 1, 2 as 2, 3 as 3, 4 as 2 + 2 or 1 + 3, 5 as 5. For the third query, in range [3, 6], all numbers i.e. 3, 4, 5 and 6 can be expressed as subset sum. For the last query, only numbers 9, 10, 11, 12, 13 can be expressed as subset sum, 9 as 5 + 2 + 2, 10 as 5 + 2 + 2 + 1, 11 as 5 + 3 + 2 + 1, 12 as 5 + 3 + 2 + 2 and 13 as 5 + 3 + 2 + 2 + 1.

Approach: The idea is to use a bitset and iterate over the array to represent all possible subset sums. The current state of bitset is defined by ORing it with the previous state of bitset left shifted X times where X is the current element processed in the array. To answer the queries in O(1) time, we can precompute the count of numbers upto every number and for a range [L, R], the answer would be pre[R] – pre[L – 1], where pre[] is the precomputed array.

Below is the implementation of the above approach.

C++

// CPP Program to answer subset
// sum queries in a given range
#include <bits/stdc++.h>
using namespace std;
 
const int MAX = 1001;
bitset<MAX> bit;
 
// precomputation array
int pre[MAX];
 
// structure to represent query
struct que {
    int L, R;
};
 
void answerQueries(int Q, que Queries[], int N,
                int arr[])
{
    // Setting bit at 0th position as 1
    bit[0] = 1;
    for (int i = 0; i < N; i++)
        bit |= (bit << arr[i]);
 
    // Precompute the array
    for (int i = 1; i < MAX; i++)
        pre[i] = pre[i - 1] + bit[i];
 
    // Answer Queries
    for (int i = 0; i < Q; i++) {
        int l = Queries[i].L;
        int r = Queries[i].R;
        cout << pre[r] - pre[l - 1] << endl;
    }
}
 
// Driver Code to test above function
int main()
{
    int arr[] = { 1, 2, 2, 3, 5 };
    int N = sizeof(arr) / sizeof(arr[0]);
    int M = 4;
    que Queries[M];
    Queries[0].L = 1, Queries[0].R = 2;
    Queries[1].L = 1, Queries[1].R = 5;
    Queries[2].L = 3, Queries[2].R = 6;
    Queries[3].L = 9, Queries[3].R = 30;
    answerQueries(M, Queries, N, arr);
    return 0;
}

Java

import java.util.Arrays;
 
// Class to represent query
class Que {
  int L, R;
 
  Que(int L, int R) {
    this.L = L;
    this.R = R;
  }
}
 
public class Main {
  private static final int MAX = 1001;
  private static boolean[] bit = new boolean[MAX];
 
  // Precomputation array
  private static int[] pre = new int[MAX];
 
  public static void answerQueries(int Q, Que[] Queries, int N, int[] arr) {
    // Setting bit at 0th position as 1
    bit[0] = true;
    for (int i = 0; i < N; i++) {
      for (int j = MAX - 1; j >= arr[i]; j--) {
        bit[j] |= bit[j - arr[i]];
      }
    }
 
    // Precompute the array
    for (int i = 1; i < MAX; i++) {
      pre[i] = pre[i - 1] + (bit[i] ? 1 : 0);
    }
 
    // Answer Queries
    for (int i = 0; i < Q; i++) {
      int l = Queries[i].L;
      int r = Queries[i].R;
      System.out.println(pre[r] - pre[l - 1]);
    }
  }
 
  // Driver Code to test above function
  public static void main(String[] args) {
    int[] arr = {1, 2, 2, 3, 5};
    int N = arr.length;
    int M = 4;
    Que[] Queries = {new Que(1, 2), new Que(1, 5), new Que(3, 6), new Que(9, 30)};
    answerQueries(M, Queries, N, arr);
  }
}

Python3

from typing import List
 
MAX = 1001
bit = [0] * MAX
 
# precomputation array
pre = [0] * MAX
 
# structure to represent query
class Que:
    def __init__(self, L, R):
        self.L = L
        self.R = R
 
def answerQueries(Q: int, Queries: List[Que], N: int, arr: List[int]) -> None:
    global bit, pre
    # Setting bit at 0th position as 1
    bit[0] = 1
    for i in range(N):
        bit = [b or (bit[j - arr[i]] if j - arr[i] >= 0 else 0) for j, b in enumerate(bit)]
 
    # Precompute the array
    for i in range(1, MAX):
        pre[i] = pre[i - 1] + bit[i]
 
    # Answer Queries
    for i in range(Q):
        l = Queries[i].L
        r = Queries[i].R
        print(pre[r] - pre[l - 1])
 
# Driver Code to test above function
if __name__ == "__main__":
    arr = [1, 2, 2, 3, 5]
    N = len(arr)
    M = 4
    Queries = [Que(1, 2), Que(1, 5), Que(3, 6), Que(9, 30)]
    answerQueries(M, Queries, N, arr)

C#

using System;
 
public class GFG
{
    private const int MAX = 1001;
    private static bool[] bit = new bool[MAX];
 
    // Precomputation array
    private static int[] pre = new int[MAX];
 
    // Class to represent query
    public class Que
    {
        public int L, R;
 
        public Que(int L, int R)
        {
            this.L = L;
            this.R = R;
        }
    }
 
    public static void answerQueries(int Q, Que[] Queries, int N, int[] arr)
    {
        // Setting bit at 0th position as 1
        bit[0] = true;
        for (int i = 0; i < N; i++)
        {
            for (int j = MAX - 1; j >= arr[i]; j--)
            {
                bit[j] |= bit[j - arr[i]];
            }
        }
 
        // Precompute the array
        for (int i = 1; i < MAX; i++)
        {
            pre[i] = pre[i - 1] + (bit[i] ? 1 : 0);
        }
 
        // Answer Queries
        for (int i = 0; i < Q; i++)
        {
            int l = Queries[i].L;
            int r = Queries[i].R;
            Console.WriteLine(pre[r] - pre[l - 1]);
        }
    }
 
    // Driver Code to test above function
    public static void Main(String[] args)
    {
        int[] arr = { 1, 2, 2, 3, 5 };
        int N = arr.Length;
        int M = 4;
        Que[] Queries = { new Que(1, 2), new Que(1, 5), new Que(3, 6), new Que(9, 30) };
        answerQueries(M, Queries, N, arr);
    }
}

Javascript

// JavaScript Program to answer subset
// sum queries in a given range
 
const MAX = 1001;
let bit = Array(MAX).fill(0);
 
// precomputation array
let pre = Array(MAX).fill(0);
 
// class to represent query
class Que {
constructor(L, R) {
this.L = L;
this.R = R;
}
}
 
function answerQueries(Q, Queries, N, arr) {
// Setting bit at 0th position as 1
bit[0] = 1;
for (let i = 0; i < N; i++) {
for (let j = MAX - 1; j >= arr[i]; j--) {
bit[j] |= bit[j - arr[i]];
}
}// Precompute the array
for (let i = 1; i < MAX; i++) {
    pre[i] = pre[i - 1] + bit[i];
}
 
// Answer Queries
for (let i = 0; i < Q; i++) {
    let l = Queries[i].L;
    let r = Queries[i].R;
    console.log(pre[r] - pre[l - 1]);
}
}
 
// Driver Code to test above function
let arr = [1, 2, 2, 3, 5];
let N = arr.length;
let M = 4;
let Queries = [new Que(1, 2), new Que(1, 5), new Que(3, 6), new Que(9, 30)];
answerQueries(M, Queries, N, arr);

Output

Time Complexity: Each query can be answered in O(1) time and precomputation requires O(MAX) time.
Auxiliary Space: O(MAX)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!