Watch 7 video solutions for The Number of Good Subsets, a hard level problem involving Array, Math, Dynamic Programming. This walkthrough by Happy Coding has 2,572 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer array nums. We call a subset of nums good if its product can be represented as a product of one or more distinct prime numbers.
nums = [1, 2, 3, 4]:
[2, 3], [1, 2, 3], and [1, 3] are good subsets with products 6 = 2*3, 6 = 2*3, and 3 = 3 respectively.[1, 4] and [4] are not good subsets with products 4 = 2*2 and 4 = 2*2 respectively.Return the number of different good subsets in nums modulo 109 + 7.
A subset of nums is any array that can be obtained by deleting some (possibly none or all) elements from nums. Two subsets are different if and only if the chosen indices to delete are different.
Example 1:
Input: nums = [1,2,3,4] Output: 6 Explanation: The good subsets are: - [1,2]: product is 2, which is the product of distinct prime 2. - [1,2,3]: product is 6, which is the product of distinct primes 2 and 3. - [1,3]: product is 3, which is the product of distinct prime 3. - [2]: product is 2, which is the product of distinct prime 2. - [2,3]: product is 6, which is the product of distinct primes 2 and 3. - [3]: product is 3, which is the product of distinct prime 3.
Example 2:
Input: nums = [4,2,3,15] Output: 5 Explanation: The good subsets are: - [2]: product is 2, which is the product of distinct prime 2. - [2,3]: product is 6, which is the product of distinct primes 2 and 3. - [2,15]: product is 30, which is the product of distinct primes 2, 3, and 5. - [3]: product is 3, which is the product of distinct prime 3. - [15]: product is 15, which is the product of distinct primes 3 and 5.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 30Problem Overview: You receive an array of integers where each value is between 1 and 30. A subset is considered good if the product of its elements can be represented as a multiplication of distinct prime numbers. The task is to count all such subsets modulo 1e9+7.
Approach 1: Bitmask Dynamic Programming (O(n + 30 * 2^10) time, O(2^10) space)
This approach relies on the fact that numbers from 1 to 30 only contain the first 10 primes: 2,3,5,7,11,13,17,19,23,29. Each number can be represented as a prime mask where each bit indicates whether a prime factor appears in its factorization. If a number contains a squared prime factor (like 4 = 2² or 12 = 2²×3), it cannot appear in a good subset and is ignored.
Build a frequency map of values in the array. Then run dynamic programming over masks where dp[mask] represents the number of ways to form a subset with that prime combination. For each valid number, compute its mask and update states by iterating existing masks and merging them if the prime sets do not overlap (mask & numMask == 0). The value 1 is handled separately since it contributes no primes; it multiplies the final result by 2^count(1). This method efficiently enumerates all valid prime combinations using bitmask states and dynamic programming.
Approach 2: Combinatorial Counting with Prime Masks (O(30 * 2^10) time, O(2^10) space)
This variation focuses on counting occurrences first and then performing transitions using combinatorics. Precompute the frequency of each number from 2 to 30. Convert every valid number into its prime mask and skip numbers containing repeated primes. Then iterate through numbers and update DP states similarly to subset DP: for every mask, add contributions from the current number multiplied by its frequency.
The difference from the previous approach is conceptual. Instead of iterating the original array, you iterate the compressed frequency list of numbers (only 30 possibilities). This reduces redundant work when the input array is large. The DP still ensures that no prime factor appears twice by checking mask overlap before combining states. This approach blends math factorization with mask-based subset construction.
Recommended for interviews: Bitmask dynamic programming is the expected solution. It shows you recognize the constraint that numbers are limited to 30, map prime factors to bits, and run subset-style DP over masks. Starting with the frequency observation and explaining why numbers with squared primes are invalid demonstrates strong reasoning. The optimal solution uses only 1024 DP states and handles the entire array efficiently.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Bitmask Dynamic Programming | O(n + 30 * 2^10) | O(2^10) | General optimal solution when numbers are limited to 1–30 and prime masks can represent factor sets |
| Combinatorial Counting with Prime Masks | O(30 * 2^10) | O(2^10) | When using frequency compression to avoid iterating the entire array repeatedly |