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

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)).