Count of Sub-Multisets With Bounded Sum Solution in Java

Ah, the classic problem of counting sub-multisets with bounded sums! It’s like trying to figure out how many ways you can pack your suitcase for a weekend trip without exceeding the weight limit. You know, the one where you always end up bringing too many shoes and not enough socks? Well, this problem is just as tricky, but thankfully, we have some code to help us navigate through the chaos!

Problem Description

Imagine you have a bag of assorted candies (or maybe just a bag of your hopes and dreams), and you want to know how many different ways you can pick these candies such that the total weight (or sweetness, if you will) doesn’t exceed a certain limit. You can pick any number of candies, including none at all (because who needs candy when you have self-control, right?).

In technical terms, you’re given a list of integers (the weights of the candies) and two integers l and r that represent the lower and upper bounds of the total weight. Your task is to count how many different combinations of these integers can be formed such that their sum lies between l and r.

Code Solution

C++
Python


class Solution {
  public int countSubMultisets(List nums, int l, int r) {
    final int kMod = 1_000_000_007;
    long[] dp = new long[r + 1];
    dp[0] = 1;
    Map count = new HashMap<>();

    for (final int num : nums)
      count.merge(num, 1, Integer::sum);

    final int zeros = count.containsKey(0) ? count.remove(0) : 0;

    for (Map.Entry entry : count.entrySet()) {
      final int num = entry.getKey();
      final int freq = entry.getValue();
      long[] stride = dp.clone();
      for (int i = num; i <= r; ++i)
        stride[i] += stride[i - num];
      for (int i = r; i > 0; --i)
        if (i >= num * (freq + 1))
          dp[i] = (stride[i] - stride[i - num * (freq + 1)]) % kMod;
        else
          dp[i] = stride[i] % kMod;
    }

    long ans = 0;
    for (int i = l; i <= r; ++i)
      ans = (ans + dp[i]) % kMod;
    return (int) (((zeros + 1) * ans) % kMod);
  }
}

Approach Explanation

The code uses dynamic programming to count the number of sub-multisets. It initializes a dp array where dp[i] represents the number of ways to form a sum of i using the given numbers. The algorithm iterates through each unique number and its frequency, updating the dp array based on the possible combinations that can be formed with that number.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n * r)
Space Complexity	O(r)

Real-World Example

Let’s say you’re at a candy store, and you have a budget of $10. You can buy different types of candies, each with a different price. You want to know how many different combinations of candies you can buy without exceeding your budget. This problem is akin to counting the sub-multisets of candy prices that sum up to a value between $5 and $10.