hard Subsets having Sum between A and B

Problem Statement

You are given an integer array nums containing n integers, integer A and integer B.

Return the number of subsets of the nums have a sum that falls between the values A and B (inclusive).

Examples

Example 1:

• Input: nums = [1, -1, 2, 3], A = 1, B = 4
• Expected Output: 10
• Justification: The subsets that satisfy the condition are: [1], [2], [3], [1, 2], [1, 3], [-1, 2], [-1, 3], [1, -1, 2], [-1, 2, 3] and [1, -1, 3]. Each of these subsets has a sum between 1 and 4.

Example 2:

• Input: nums = = [3, 5, -7], A = -4, B = 3
• Expected Output: 5
• Justification: The subsets that satisfy the condition are: [], [3], [5, -7], [3, -7], and [3, 5, -7]. Each of these subsets has a sum between -4 and 3.

Example 3:

• Input: nums = [4, 1, -2, 7, -3], A = 0, B = 6
• Expected Output: 16
• Justification: There are a total 16 subsets which have a sum in the range 0 to 6.

Solution

To solve the problem of counting subsets whose sums fall within a specific range, we use the Meet in the middle approach. The idea is to divide the original array into two halves and then generate all possible subset sums for each half. By working with smaller subsets, we reduce the problem's complexity, making it more manageable. The sums of subsets from the first half are stored in one list, while the sums from the second half are stored in another. The second list is then sorted to enable efficient binary search operations.

After generating and sorting these subset sums, we determine how many pairs of sums from the two lists fall within the given range ([A, B]). For each sum from the first list, we calculate the required range in the second list using simple arithmetic adjustments. Binary search is then employed to quickly count how many sums in the second list fall within this adjusted range. The total count of such valid subsets is returned as the final result. This method significantly reduces the time complexity compared to a brute-force approach, making it effective for handling larger arrays.

Step-by-Step Algorithm

1. Calculate the Length and Midpoint of the Array:

   • Start by calculating the length of the input array nums and store it in the variable n.
   • Calculate the midpoint of the array using n / 2 and store it in the variable mid. This will allow us to split the array into two halves.

2. Split the Array into Two Halves:

   • Use the Arrays.copyOfRange method to create two new arrays: set1 and set2.
   • set1 contains elements from the start of nums to the midpoint, i.e., nums[0] to nums[mid-1].
   • set2 contains elements from the midpoint to the end of nums, i.e., nums[mid] to nums[n-1].

3. Generate All Possible Subset Sums for set1:

   • Call the generateSubsetSums method with set1 as the input.
   • The method returns the list sum1 containing all possible subset sums of set1.

4. Generate All Possible Subset Sums for set2:

   • Similarly, call the generateSubsetSums method with set2 as the input.
   • The process is identical to the one used for set1.
   • The method returns the list sum2 containing all possible subset sums of set2.

5. Sort the List of Subset Sums for set2:

   • Use Collections.sort to sort the list sum2. Sorting this list allows us to efficiently find how many subset sums fall within a specific range using binary search.

6. Initialize a Count Variable:

   • Initialize a variable count to 0. This will be used to keep track of the total number of valid subsets whose sum lies between A and B.

7. Iterate Over Each Sum in sum1:

   • Use a loop to iterate through each sum s1 in sum1.
   • For each s1, calculate the low and high bounds:
     • low = A - s1: This is the lower bound of the desired sum range when combined with a sum from sum2.
     • high = B - s1: This is the upper bound of the desired sum range when combined with a sum from sum2.
   • This step finds the lower and upper bound of the range in sum2.

8. Count Valid Sums in sum2:

   • Call the countInRange method with sum2, low, and high as arguments.
   • Inside the countInRange method:
     • Call lowerBound to find the first index in sum2 where the elements are not less than low.
     • Call upperBound to find the first index in sum2 where the elements are greater than high.
     • The difference right - left gives the count of valid sums in sum2 that fall within the range [low, high].
   • Add this count to the total count.

9. Return the Total Count:

   • After iterating through all sums in sum1, return the final value of count. This value represents the total number of subsets whose sum is within the range [A, B].

Algorithm Walkthrough

1. Input Preparation:

   • We start with the array nums = [1, -1, 2, 3] and the range [A, B] = [1, 4].
   • Calculate the midpoint mid = 4 / 2 = 2.

2. Split the Array:

   • Split nums into two halves:
     • set1 = [1, -1]
     • set2 = [2, 3]

3. Generate Subset Sums for set1:

   • Generate all possible subset sums for set1 = [1, -1]:
     • Subset [] → Sum 0
     • Subset [1] → Sum 1
     • Subset [-1] → Sum -1
     • Subset [1, -1] → Sum 0
   • Resulting list sum1 = [0, 1, -1, 0]

4. Generate Subset Sums for set2:

   • Generate all possible subset sums for set2 = [2, 3]:
     • Subset [] → Sum 0
     • Subset [2] → Sum 2
     • Subset [3] → Sum 3
     • Subset [2, 3] → Sum 5
   • Resulting list sum2 = [0, 2, 3, 5]

5. Sort sum2:

   • Sort sum2, though it is already sorted in this case: sum2 = [0, 2, 3, 5].

6. Count Valid Subsets:

   • Initialize count = 0.

   • Iterate over each sum s1 in sum1 and calculate the range [low, high] for valid sums in sum2:

     • For s1 = 0:
       • low = 1 - 0 = 1
       • high = 4 - 0 = 4
       • In sum2, valid sums are 2 and 3.
       • Valid subset count = 2.
       • Update count = count + 2 = 2.
     • For s1 = 1:
       • low = 1 - 1 = 0
       • high = 4 - 1 = 3
       • In sum2, valid sums are 0, 2, and 3.
       • Valid subset count = 3.
       • Update count = count + 3 = 5.
     • For s1 = -1:
       • low = 1 - (-1) = 2
       • high = 4 - (-1) = 5
       • In sum2, valid sums are 2, 3, and 5.
       • Valid subset count = 3.
       • Update count = count + 3 = 8.
     • For s1 = 0:
       • low = 1 - 0 = 1
       • high = 4 - 0 = 4
       • In sum2, valid sums are 2 and 3.
       • Valid subset count = 2.
       • Update count = count + 2 = 10.

7. Final Output:

   • After processing all sums in sum1, the final count of valid subsets is 10.
   • Return 10 as the output.

Code

import java.util.*;

public class Solution {

  // Count the number of subsets whose sum falls between A and B, inclusive
  public int countSubsets(int[] nums, int A, int B) {
    int n = nums.length;
    int mid = n / 2;

    // Split the array into two halves
    int[] set1 = Arrays.copyOfRange(nums, 0, mid);
    int[] set2 = Arrays.copyOfRange(nums, mid, n);

    // Generate all possible subset sums for both halves
    List<Integer> sum1 = generateSubsetSums(set1);
    List<Integer> sum2 = generateSubsetSums(set2);

    // Sort sum2 for binary search
    Collections.sort(sum2);

    int count = 0;

    // For each sum in sum1, find the number of valid sums in sum2 that together fall within [A, B]
    for (int s1 : sum1) {
      int low = A - s1; // Lower bound of range in sum2
      int high = B - s1; // Upper bound of range in sum2
      count += countInRange(sum2, low, high); // Count sums in range [low, high]
    }

    return count; // Return the total count of valid subsets
  }

  // Generate all possible subset sums for a given set
  private List<Integer> generateSubsetSums(int[] set) {
    List<Integer> result = new ArrayList<>();
    int n = set.length;
    // Iterate over all possible subsets using bitmask
    for (int i = 0; i < (1 << n); i++) {
      int sum = 0;
      // Calculate the sum of the current subset
      for (int j = 0; j < n; j++) {
        if ((i & (1 << j)) > 0) {
          sum += set[j];
        }
      }
      result.add(sum); // Add the subset sum to the result list
    }
    return result; // Return the list of all subset sums
  }

  // Count the number of elements in sortedList within the range [low, high]
  private int countInRange(List<Integer> sortedList, int low, int high) {
    int left = lowerBound(sortedList, low); // Find the lower bound of low
    int right = upperBound(sortedList, high); // Find the upper bound of high
    return right - left; // Return the count of elements in the range
  }

  // Find the first position where elements are not less than target
  private int lowerBound(List<Integer> sortedList, int target) {
    int low = 0,
      high = sortedList.size();
    while (low < high) {
      int mid = low + (high - low) / 2;
      if (sortedList.get(mid) < target) {
        low = mid + 1; // Move to the right side
      } else {
        high = mid; // Move to the left side
      }
    }
    return low; // Return the position of the lower bound
  }

  // Find the first position where elements are greater than target
  private int upperBound(List<Integer> sortedList, int target) {
    int low = 0,
      high = sortedList.size();
    while (low < high) {
      int mid = low + (high - low) / 2;
      if (sortedList.get(mid) <= target) {
        low = mid + 1; // Move to the right side
      } else {
        high = mid; // Move to the left side
      }
    }
    return low; // Return the position of the upper bound
  }

  // Main method to test the solution
  public static void main(String[] args) {
    Solution solution = new Solution();

    int[] nums1 = { 1, -1, 2, 3 };
    System.out.println(solution.countSubsets(nums1, 1, 4)); // Output: 10

    int[] nums2 = { 3, 5, -7 };
    System.out.println(solution.countSubsets(nums2, -4, 3)); // Output: 5

    int[] nums3 = { 4, 1, -2, 7, -3 };
    System.out.println(solution.countSubsets(nums3, 0, 6)); // Output: 16
  }
}

Complexity Analysis

Time Complexity

• Generating Subset Sums:
  • For each of the two halves of the array (Set1 and Set2), the code generates all possible subset sums. Since there are N/2 elements in each half, the number of subsets is 2^(N/2). This gives us O(2^(N/2)) operations for each half.
• Sorting the Subset Sums (Sum2):
  • Sorting the Sum2 list takes O(2^(N/2) * log(2^(N/2))), which simplifies to O(2^(N/2) * N/2) or O(N * 2^(N/2)).
• Binary Search Operations:
  • For each sum in Sum1, we perform a binary search on Sum2 to count the number of valid pairs. This step takes O(2^(N/2) * log(2^(N/2)))orO(2^(N/2) * N/2).
• Total Time Complexity:
  • The overall time complexity is O(2^(N/2) * N).

Space Complexity

• Storage for Subset Sums (Sum1 and Sum2):
  • We need to store the subset sums for both halves, which requires O(2^(N/2)) space for each list. Thus, the total space complexity is O(2^(N/2)).