Skip to main content
Talentd

Count of Sub-Multisets With Bounded Sum - Solution & Explanation

HardArrayHash TableDynamic ProgrammingSliding Window18 min read
Practice this problem

Problem Statement

You are given a 0-indexed array nums of non-negative integers, and two integers l and r.

Return the count of sub-multisets within nums where the sum of elements in each subset falls within the inclusive range of [l, r].

Since the answer may be large, return it modulo 109 + 7.

A sub-multiset is an unordered collection of elements of the array in which a given value x can occur 0, 1, ..., occ[x] times, where occ[x] is the number of occurrences of x in the array.

Note that:

  • Two sub-multisets are the same if sorting both sub-multisets results in identical multisets.
  • The sum of an empty multiset is 0.

 

Example 1:

Input: nums = [1,2,2,3], l = 6, r = 6
Output: 1
Explanation: The only subset of nums that has a sum of 6 is {1, 2, 3}.

Example 2:

Input: nums = [2,1,4,2,7], l = 1, r = 5
Output: 7
Explanation: The subsets of nums that have a sum within the range [1, 5] are {1}, {2}, {4}, {2, 2}, {1, 2}, {1, 4}, and {1, 2, 2}.

Example 3:

Input: nums = [1,2,1,3,5,2], l = 3, r = 5
Output: 9
Explanation: The subsets of nums that have a sum within the range [3, 5] are {3}, {5}, {1, 2}, {1, 3}, {2, 2}, {2, 3}, {1, 1, 2}, {1, 1, 3}, and {1, 2, 2}.

 

Constraints:

  • 1 <= nums.length <= 2 * 104
  • 0 <= nums[i] <= 2 * 104
  • Sum of nums does not exceed 2 * 104.
  • 0 <= l <= r <= 2 * 104

Approach Overview

Problem Overview: You receive an integer array that represents a multiset. The task is to count how many sub-multisets have a total sum within a range [l, r]. Since duplicates are allowed and each value can be used multiple times (up to its frequency), the problem becomes a bounded subset-sum counting problem.

Approach 1: Dynamic Programming with Sliding Window Optimization (O(U * r) time, O(r) space)

Start by compressing the array into a frequency map using a hash table. Each unique value v appears cnt times. Define a DP array where dp[s] represents the number of ways to build sum s. This resembles a bounded knapsack problem. For each value, update the DP states using a prefix-sum or sliding window trick so you avoid iterating cnt times explicitly. The window maintains contributions from dp[s - k*v] for k within the allowed count. This optimization reduces the transition from O(cnt * r) to O(r). The final answer is the sum of dp[s] for s between l and r. The approach relies heavily on dynamic programming with a window-style prefix sum similar to techniques used in sliding window problems.

Approach 2: Combinatorial Counting with Frequency Compression (O(U * r) time, O(r) space)

Instead of thinking about individual elements, treat the array as groups of identical values. For each value v with frequency cnt, you can pick it 0..cnt times. The total contribution to the sum is therefore k * v. Build a DP array that counts combinations while iterating over unique values. For every sum s, accumulate contributions from valid previous states while respecting the upper bound on how many times v can appear. Prefix sums or difference arrays help efficiently subtract states that exceed the allowed count. This turns the naive combinatorial enumeration into a linear scan over possible sums. The technique is conceptually similar to generating function multiplication but implemented iteratively with arrays.

Recommended for interviews: The optimized dynamic programming approach is what interviewers typically expect. Recognizing that the problem is a bounded knapsack variant shows good pattern recognition. Implementing the prefix-sum sliding window optimization demonstrates strong DP skills and avoids the quadratic blow-up that a naive DP would cause.

Approach 1: Dynamic Programming Approach

This approach leverages dynamic programming to track possible sums using a bitset or a boolean array up to the maximum possible sum. Initially, the set only contains the empty sub-multiset sum of zero. We iterate over each number in the given array, updating the set of attainable sums by considering each number's contribution to prior sums. Once we compute all possible sums, we count those within the range [l, r]. To handle large outputs, a modulus operation is employed, complying with the problem constraints.

In this C solution, we use an array dp to keep track of the attainable sums. We initialize dp[0] as 1 to signify the empty set. As we iterate through each number, we update the sum possibilities in the array by iterating in reverse order to prevent over-counting. Once all possible sums are identified, we sum the relevant counts within [l, r].

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * m), where n is the number of elements and m is the maximum sum, Space Complexity: O(m), where m is the maximum boundary for sums.

Try this approach in the editor →

Approach 2: Combinatorial Counting Approach

This approach uses combinatorial counting with inclusion-exclusion principle. For each number in the array, we compute how many times each sum can be formed and employ counting techniques to find the number of subsets in the range [l, r]. This can involve computing all subset sums for all combinations of numbers, but uses inclusion-exclusion principles and combinatorial calculations to efficiently tally possible subset counts.

This C solution outlines the structure for a combinatorial counting method based on binomial coefficients. However, implementing full combinatorial logic is intricate, especially for large ranges, and typically more efficiently codified in higher-level languages supporting big integer computations.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

The time complexity of computing binomial coefficients typically exceeds O(2^n) in a naive implementation, with space complexity directly proportional to the subset totals reviewed.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming Approach

Time Complexity: O(n * m), where n is the number of elements and m is the maximum sum, Space Complexity: O(m), where m is the maximum boundary for sums.

Combinatorial Counting Approach

The time complexity of computing binomial coefficients typically exceeds O(2^n) in a naive implementation, with space complexity directly proportional to the subset totals reviewed.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming with Sliding WindowO(U * r)O(r)General case; optimal solution for bounded subset-sum counting
Combinatorial Counting with Frequency CompressionO(U * r)O(r)Useful when reasoning about combinations of identical values

Video Solution

2902. Count of Sub-Multisets With Bounded Sum | Leetcode Biweekly 115 • codingMohan • 1,980 views views

Watch 2 more video solutions →

Frequently Asked Questions

Is Count of Sub-Multisets With Bounded Sum easy or hard?
Count of Sub-Multisets With Bounded Sum is a Hard problem. The difficulty comes from recognizing the bounded knapsack structure and optimizing transitions with prefix sums or sliding window techniques to avoid O(n * r * freq) complexity.
Count of Sub-Multisets With Bounded Sum Python/Java solution
Implement a DP array of size r+1 and process values grouped by frequency. For each value, update reachable sums using prefix-sum sliding window optimization so you respect the maximum count of that number. The same logic works in Python, Java, C++, C#, and JavaScript.
How to solve Count of Sub-Multisets With Bounded Sum in O(n)?
The problem cannot generally be solved in strict O(n) time because every reachable sum up to r must be considered. The closest practical bound is O(U * r) using dynamic programming with prefix-sum sliding window optimization, which avoids the extra factor caused by element frequency.
What is the best approach for Count of Sub-Multisets With Bounded Sum?
The best approach uses dynamic programming with frequency compression and sliding window optimization. Treat the problem as a bounded knapsack where each value can be used up to its frequency. By maintaining prefix sums while updating the DP array, transitions can be computed in O(r) per unique value instead of iterating over all counts.
Is Count of Sub-Multisets With Bounded Sum asked at Google/Amazon/Meta?
Problems based on bounded subset sum and multiset counting frequently appear in interviews at companies like Google, Amazon, and Meta. Variants test dynamic programming, frequency compression, and optimization techniques such as prefix sums or sliding window transitions.
What data structure is used in Count of Sub-Multisets With Bounded Sum?
The main data structures are a hash table for counting frequencies and a dynamic programming array for storing the number of ways to achieve each sum. Prefix sums or sliding window accumulators are used to optimize transitions between DP states.
What is the time complexity of Count of Sub-Multisets With Bounded Sum?
The optimized solution runs in O(U * r) time where U is the number of unique values in the array and r is the upper bound of the sum range. Space complexity is O(r) because only a single DP array of size r+1 is maintained.

Ready to solve this problem?

Practice Count of Sub-Multisets With Bounded Sum with our built-in code editor and test cases.

Practice on FleetCode
Previous

Coin Change

Next

Coin Change II