Count of Sub-Multisets With Bounded Sum - Practice Coding Problems

Count of Sub-Multisets With Bounded Sum - Problem

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, 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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,2,2], l = 1, r = 4

› Output: 4

💡 Note: Valid sub-multisets: [1] (sum=1), [2] (sum=2), [1,2] (sum=3), [2,2] (sum=4). All sums are in range [1,4].

Example 2 — With Zeros

$ Input: nums = [0,1,2], l = 1, r = 3

› Output: 4

💡 Note: Valid sub-multisets: [1] (sum=1), [2] (sum=2), [1,2] (sum=3), [0,1,2] (sum=3). The zero can be included or excluded.

Example 3 — No Valid Sums

$ Input: nums = [1,2,3], l = 10, r = 15

› Output: 0

💡 Note: Maximum possible sum is 1+2+3=6, which is less than l=10. No valid sub-multisets exist.

Constraints

1 ≤ nums.length ≤ 2 × 10⁴
0 ≤ nums[i] ≤ 2 × 10⁴
1 ≤ l ≤ r ≤ 2.5 × 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Array nums and range [l, r]

Process

Generate all possible sub-multisets and check sum ranges

Output

Count of valid sub-multisets

Key Takeaway

🎯 Key Insight: Use frequency counting + dynamic programming to efficiently count sub-multisets without generating duplicates

Asked in

G Google 15 f Meta 12 a Amazon 8

The key insight is to use dynamic programming with frequency counting to avoid generating duplicate sub-multisets. Count frequency of each unique element, then use DP where dp[sum] represents ways to achieve that sum. Handle zeros separately for optimization. Best approach is optimized DP. Time: O(n × r), Space: O(r)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force with Backtracking	O(2^n)	O(n)	Generate all possible sub-multisets and count those with sums in [l, r]
Optimized DP with Space Reduction	O(n × r)	O(r)	Use optimized DP with better space management and early termination
Dynamic Programming with Frequency Count	O(n × r)	O(r)	Count frequencies, then use DP to compute number of ways to achieve each sum

Brute Force with Backtracking — Algorithm Steps

Step 1: Count frequency of each unique element
Step 2: Use backtracking to generate all combinations
Step 3: For each valid sum in [l, r], increment counter

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Frequencies

Count how many times each number appears

Backtrack

Try all possible counts for each unique number

Check Range

Count valid sums in [l, r]

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MOD 1000000007
#define MAX_NUM 1000

int freq[MAX_NUM + 1];
int uniqueNums[MAX_NUM];
int uniqueCount;

int backtrack(int idx, int currentSum, int l, int r) {
    if (idx == uniqueCount) {
        return (l <= currentSum && currentSum <= r) ? 1 : 0;
    }
    
    int count = 0;
    int num = uniqueNums[idx];
    for (int copies = 0; copies <= freq[num]; copies++) {
        int newSum = currentSum + num * copies;
        if (newSum <= r) {
            count = (count + backtrack(idx + 1, newSum, l, r)) % MOD;
        }
    }
    return count;
}

int solution(int* nums, int numsSize, int l, int r) {
    memset(freq, 0, sizeof(freq));
    uniqueCount = 0;
    
    for (int i = 0; i < numsSize; i++) {
        if (freq[nums[i]] == 0) {
            uniqueNums[uniqueCount++] = nums[i];
        }
        freq[nums[i]]++;
    }
    
    return backtrack(0, 0, l, r);
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int l, r;
    scanf("%d", &l);
    scanf("%d", &r);
    
    printf("%d\n", solution(nums, numsSize, l, r));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

In worst case, we explore all possible combinations of elements

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth and frequency map storage

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~35 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force with Backtracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler