We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count of Sub-Multisets With Bounded Sum

Difficulty: Hard

Problem Description

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 10^9 + 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.

Key Insights

  • A sub-multiset can contain elements in varying frequencies based on their occurrences in the original array.
  • The challenge is to efficiently count the valid sub-multisets that achieve a sum within a specific range.
  • Dynamic programming can be utilized to build up the count of valid sums incrementally.
  • The problem can be broken down into smaller subproblems using combinatorial methods.

Space and Time Complexity

Time Complexity: O(n * S), where n is the number of unique elements and S is the sum of the elements. Space Complexity: O(S), where S is the sum of the elements to store counts of sums.

Solution

To solve the problem, we can use a dynamic programming approach to count the number of ways to form different sums using the available elements. We maintain a frequency map of the elements and then use a DP array to keep track of reachable sums. For each unique element, we iterate through possible sums and update the DP array based on the number of occurrences of that element.

Code Solutions

def countSubmultisets(nums, l, r):
    MOD = 10**9 + 7
    max_sum = sum(nums)
    
    # Frequency array for unique elements
    freq = {}
    for num in nums:
        if num in freq:
            freq[num] += 1
        else:
            freq[num] = 1
    
    # DP array to count ways to achieve sums
    dp = [0] * (max_sum + 1)
    dp[0] = 1  # Base case: one way to make sum 0 (empty set)
    
    for num, count in freq.items():
        # Update dp array for current number
        for j in range(max_sum, num - 1, -1):
            for k in range(1, count + 1):
                if j >= num * k:
                    dp[j] = (dp[j] + dp[j - num * k]) % MOD
    
    # Count valid sums in range [l, r]
    result = 0
    for s in range(l, r + 1):
        result = (result + dp[s]) % MOD
    
    return result
← Back to All Questions