Count of Sub-Multisets With Bounded Sum Solution in C++

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 vacation without exceeding the weight limit. You know, the one where you always end up bringing back more than you took? Well, this problem is a bit like that, but with numbers instead of clothes.

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 some of them without exceeding a certain weight limit. But wait! There’s a twist! You can pick the same candy multiple times, but you can’t exceed a certain total weight. Sounds fun, right?

In technical terms, the problem asks you to count the number of sub-multisets of a given list of integers (let’s call them nums) such that the sum of the integers in each sub-multiset lies between two bounds, l and r.

Solution Links

Before we dive into the code, here are some handy buttons for you to explore solutions in other languages:

Code Solution


class Solution {
 public:
  int countSubMultisets(vector& nums, int l, int r) {
    constexpr int kMod = 1'000'000'007;
    vector dp(r + 1);
    dp[0] = 1;
    unordered_map count;

    for (const int num : nums)
      ++count[num];

    const int zeros = count[0];
    count.erase(0);

    for (const auto& [num, freq] : count) {
      vector stride = dp;
      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 ((zeros + 1) * ans) % kMod;
  }
};

Approach Explanation

The code uses dynamic programming to solve the problem efficiently. It maintains a dp array where dp[i] represents the number of sub-multisets that sum up to i. The algorithm iterates through each unique number in the input list, updating the dp array based on the frequency of each number. It cleverly uses a stride array to accumulate the counts of sub-multisets for each possible sum, ensuring that the constraints of the problem are respected.

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 as many of your favorite candy as you want, but you can’t exceed that budget. If you have candies priced at $1, $2, and $3, how many different combinations can you buy without going over $10? This is essentially what the problem is asking, and the solution helps you figure out all the possible combinations of candies (or numbers) you can buy without breaking the bank!