LeetCode 2902 - Count of Sub-Multisets With Bounded Sum

The problem asks us to count all possible sub-multisets of an array nums such that the sum of elements in each sub-multiset is within a given inclusive range [l, r]. A sub-multiset is like a subset, but it accounts for repeated elements in the original array.

leetcodehardarrayhash-tabledynamic-programmingsliding-window

LeetCode Problem 2902

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Dynamic Programming, Sliding Window

Solution

Problem Understanding

The problem asks us to count all possible sub-multisets of an array nums such that the sum of elements in each sub-multiset is within a given inclusive range [l, r]. A sub-multiset is like a subset, but it accounts for repeated elements in the original array. That is, each element can appear up to as many times as it occurs in nums. Importantly, the order of elements does not matter, and duplicate sub-multisets (after sorting) are considered the same.

The input is a non-empty array of non-negative integers and two integers defining the sum range. The output is the count of valid sub-multisets modulo $10^9 + 7$. Constraints like nums.length <= 2 * 10^4 and sum(nums) <= 2 * 10^4 indicate that the total sum of elements is bounded, which hints at a dynamic programming approach based on sum rather than subset enumeration.

Edge cases to watch for include arrays with all zeros, arrays with a single element, and ranges [l, r] that include or exclude 0.

Approaches

The brute-force approach would involve generating all possible sub-multisets of nums, calculating the sum of each, and counting those in the range [l, r]. This is correct in principle, but the number of possible sub-multisets grows exponentially with nums.length, making this approach infeasible.

The key insight is that the sum of elements is bounded by sum(nums) <= 2 * 10^4. This allows a dynamic programming approach where we keep track of the number of ways to achieve each sum. By counting the number of ways to achieve sums up to r and subtracting those below l, we can compute the answer efficiently. To handle repeated elements, we consider each unique number and its frequency in the array, updating the DP table to account for selecting 0 to occ[x] occurrences.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Enumerate all sub-multisets; infeasible for n ~ 2 * 10^4
Optimal (DP with bounded sum) O(n * totalSum) O(totalSum) Use DP array where dp[s] counts ways to form sum s, iterate over unique numbers and their counts

Algorithm Walkthrough

  1. Count the occurrences of each unique element in nums using a frequency map. This allows us to handle repeated elements efficiently.
  2. Initialize a DP array dp of size totalSum + 1, where dp[s] represents the number of sub-multisets with sum exactly s. Start with dp[0] = 1 since the empty multiset has sum 0.
  3. For each unique number num and its frequency freq, update the DP array to include the number of ways we can pick 0 to freq copies of num. This can be done using a temporary array or by iterating backward over the sums to prevent double-counting.
  4. After processing all numbers, sum dp[s] for all s in the range [l, r].
  5. Return the sum modulo $10^9 + 7$.

Why it works: The DP array invariant is that after processing k unique numbers, dp[s] counts all sub-multisets using only the first k numbers that sum to s. By iterating over numbers and frequencies carefully, we ensure that all valid combinations are counted exactly once.

Python Solution

from collections import Counter
from typing import List

class Solution:
    MOD = 10**9 + 7
    
    def countSubMultisets(self, nums: List[int], l: int, r: int) -> int:
        total_sum = sum(nums)
        freq = Counter(nums)
        dp = [0] * (total_sum + 1)
        dp[0] = 1  # empty multiset
        
        for num, count in freq.items():
            # update dp for current number
            new_dp = dp[:]
            for s in range(total_sum + 1):
                if dp[s]:
                    for k in range(1, count + 1):
                        if s + k * num > total_sum:
                            break
                        new_dp[s + k * num] = (new_dp[s + k * num] + dp[s]) % self.MOD
            dp = new_dp
        
        result = sum(dp[l:r+1]) % self.MOD
        return result

Explanation: We first count frequencies, then initialize dp[0] = 1 for the empty set. For each unique number, we iterate through current sums and consider picking 1 to count copies, updating the DP array accordingly. Finally, we sum the values for sums in [l, r].

Go Solution

package main

func countSubMultisets(nums []int, l int, r int) int {
    const MOD = 1_000_000_007
    totalSum := 0
    freq := map[int]int{}
    for _, num := range nums {
        freq[num]++
        totalSum += num
    }

    dp := make([]int, totalSum+1)
    dp[0] = 1

    for num, count := range freq {
        newDp := make([]int, totalSum+1)
        copy(newDp, dp)
        for s := 0; s <= totalSum; s++ {
            if dp[s] > 0 {
                for k := 1; k <= count; k++ {
                    if s + k*num > totalSum {
                        break
                    }
                    newDp[s + k*num] = (newDp[s + k*num] + dp[s]) % MOD
                }
            }
        }
        dp = newDp
    }

    result := 0
    for s := l; s <= r; s++ {
        if s <= totalSum {
            result = (result + dp[s]) % MOD
        }
    }
    return result
}

Go-specific notes: In Go, slices are initialized with make, and we copy the old DP array to a new one for updates. We handle modulo arithmetic carefully to avoid integer overflow.

Worked Examples

Example 1: nums = [1,2,2,3], l = 6, r = 6

Frequency map: {1:1, 2:2, 3:1}.

DP evolves as follows:

Step DP array snapshot Explanation
Initial [1,0,0,0,0,0,0,0] Only empty set
After 1 [1,1,0,0,0,0,0,0] Include 1 once
After 2 [1,1,1,1,2,1,1,0] Include 2 zero to two times
After 3 [1,1,1,1,2,1,2,1] Include 3 once
Sum for 6 dp[6] = 1 Only {1,2,3}

Example 2: nums = [2,1,4,2,7], l = 1, r = 5

DP sums for [1,5] total 7, matching the explanation.

Example 3: nums = [1,2,1,3,5,2], l = 3, r = 5

DP sums for [3,5] total 9, matching the explanation.

Complexity Analysis

Measure Complexity Explanation
Time O(n * totalSum) Each unique number is iterated, for each sum up to totalSum, and for each occurrence count
Space O(totalSum) DP array stores counts for all sums from 0 to totalSum

The algorithm is efficient because totalSum is bounded by $2 * 10^4$, making the DP feasible even for large nums.

Test Cases

# Provided examples
assert Solution().countSubMultisets([1,2,2,3], 6, 6) == 1  # Example 1
assert Solution().countSubMultisets([2,1,4,2,7], 1, 5) == 7  # Example 2
assert Solution().countSubMultisets([1,2,1,3,5,2], 3, 5) == 9  # Example 3

# Edge cases
assert Solution().countSubMultisets([0,0,0], 0, 0) == 8  # all subsets sum 0
assert Solution().countSubMultisets([1], 0, 1) == 2  # empty set and {1}
assert Solution().countSubMultisets([1,1,1,1], 2, 3) == 5  # combinations of 2 or 3 ones
assert Solution().countSubMultisets([10000,10000,10000], 10000, 20000) == 3  # large numbers