The Number of Good Subsets: Bitmask DP Over Primes
LeetCode The Number of Good Subsets (Problem 1994) gives you an integer array nums. A good subset is a non-empty subset of nums where the product of its elements can be represented as a product of one or more distinct prime numbers. Return the number of different good subsets, modulo 10^9 + 7.
For example, given nums = [1, 2, 3, 4], the good subsets are [1, 2], [1, 3], [1, 2, 3], [2], [3], and [2, 3]. The subset [4] is not good because 4 = 2 * 2, and the prime factor 2 repeats. The answer is 6.
The constraints say 1 <= nums[i] <= 30. That cap is the entire trick.
Why this problem matters
This problem sits at the intersection of number theory and bitmask DP. You need to recognize that the small value range (1 to 30) means only 10 primes are relevant, and those 10 primes fit neatly into a 10-bit bitmask. That transforms a combinatorial explosion into a manageable state space. Problems that combine prime factorization with bitmask enumeration appear often in competitive programming, and the pattern transfers directly to other "subset with constraints" problems.
Key insight: prime bitmasks
There are exactly 10 primes up to 30: 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29. Since every number in the array is at most 30, its prime factorization only involves these 10 primes.
A good subset requires no repeated prime factors in the product. That means:
-
Invalid numbers: Any number with a squared prime factor (like 4 = 2 x 2, 8 = 2 x 2 x 2, 9 = 3 x 3, 12, 16, 18, 20, 24, 25, 27, 28) can never appear in a good subset. Skip them entirely.
-
Valid numbers: Numbers like 2, 3, 5, 6 (= 2 x 3), 7, 10 (= 2 x 5), etc. have all distinct prime factors. Represent each valid number as a bitmask over the 10 primes.
-
The number 1 is special: It has no prime factors at all. Including any number of 1s in a subset never creates a repeated prime. Handle 1s separately by baking
pow(2, count_of_ones)into the DP base case.
Since we only need 10 bits, the total state space is 2^10 = 1024 masks. That is tiny.
The approach
Define dp[mask] as the number of ways to form a subset of the processed numbers whose product has exactly the set of prime factors indicated by mask.
Base case: dp[0] = pow(2, count_of_ones). This accounts for every possible combination of 1s that can be included alongside any subset. Each copy of 1 can independently be present or absent without affecting prime factors.
Transition: For each valid number v (from 2 to 30) with prime mask m and count c in the array, iterate over all existing masks. If existing & m == 0 (no overlapping primes), then dp[existing | m] += dp[existing] * c.
Answer: Sum dp[mask] for all mask > 0. The 1s are already baked into the base case, so no separate multiplication is needed.
Clean Python solution
def numberOfGoodSubsets(nums):
MOD = 10**9 + 7
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
cnt = [0] * 31
for x in nums:
cnt[x] += 1
def prime_mask(n):
mask = 0
for i, p in enumerate(primes):
if n % p == 0:
n //= p
if n % p == 0:
return -1
mask |= 1 << i
return mask
dp = [0] * 1024
dp[0] = pow(2, cnt[1], MOD)
for v in range(2, 31):
if cnt[v] == 0:
continue
m = prime_mask(v)
if m < 0:
continue
for mask in range(1023, -1, -1):
if dp[mask] and (mask & m) == 0:
dp[mask | m] = (dp[mask | m] + dp[mask] * cnt[v]) % MOD
return sum(dp[1:]) % MOD
Step-by-step walkthrough
Let's trace the DP with a small example: nums = [2, 3, 6, 5]. The valid numbers are 2 (mask bit 0), 3 (mask bit 1), 6 = 2 x 3 (mask bits 0 and 1), and 5 (mask bit 2).
Step 1: Initialize dp[0] = 1 (empty subset)
The base case: there is exactly 1 way to form a product with no prime factors (the empty subset).
Step 2: Process number 2 (prime mask = bit 0)
For each existing mask that does not overlap with 2's mask, we add dp[existing] to dp[existing | mask(2)].
Step 3: Process number 3 (prime mask = bit 1)
Now dp[0]=1, dp[1]=1, dp[2]=1, dp[3]=1. Four masks are populated.
Step 4: Process number 6 = 2 x 3 (prime mask = bits 0,1 = 0b11)
Only dp[0] has no overlap with 6's mask. dp[3] goes from 1 to 2, because both {2,3} and {6} produce primes 2 and 3.
Step 5: Process number 5 (prime mask = bit 2)
Bit 2 does not conflict with any existing mask, so 5 combines with every populated state. The answer sums all dp[mask] for mask > 0.
Step 6: Account for 1s via the base case
The number 1 has no prime factors, so including it never creates a repeated prime. With k copies of 1, dp[0] starts at 2^k, propagating through all transitions.
The key moment is Step 4, where number 6 (with mask 0b11) can only combine with masks that have both bits 0 and 1 clear. Only the empty mask qualifies, so 6 contributes to dp[3] but cannot pair with subsets already containing 2 or 3. This is exactly the "no overlapping primes" constraint enforced by the bitwise AND check.
Complexity analysis
| Aspect | Value |
|---|---|
| Time | O(n + 30 * 2^10) |
| Space | O(2^10) |
Building the frequency count takes O(n). The DP iterates over at most 29 valid numbers (2 to 30), and for each one scans all 1024 masks. That gives 29 * 1024 = roughly 30,000 operations, which is constant. The dp array has 1024 entries. Total space is O(1024) = O(1) beyond the input.
The building blocks
Bitmask DP. Representing a set of chosen elements as a bitmask and using mask & new == 0 to check compatibility is a fundamental technique. You see it in traveling salesman, set cover, and any problem where you need to track "which items have been used" with a small universe.
Prime factorization. Breaking each number into its prime factors and checking for squared factors is the preprocessing step that classifies numbers as valid or invalid. The small range (1 to 30) makes trial division perfectly efficient.
Modular arithmetic. The answer can be astronomically large, so you work modulo 10^9 + 7 throughout. The key operation is pow(2, cnt[1], MOD) for the base case, which uses modular exponentiation to handle potentially millions of 1s efficiently.
Edge cases
All 1s. If the array contains only 1s, the answer is 0. The problem requires the product to be a product of one or more distinct primes. A product of 1 does not qualify because it contains zero primes. No valid numbers (2 to 30) exist, so the DP loop does nothing and sum(dp[1:]) returns 0.
Single element. If the array has one valid number (like 2, 3, 5, 6, etc.), the answer is 1. If the only element is 1 or an invalid number (like 4), the answer is 0.
All invalid numbers. If every element is something like 4, 8, 9, 16, etc., no good subset exists. The answer is 0.
Large count of the same number. If you have 100,000 copies of 2, you can include at most one of them in a good subset (because 2 x 2 repeats the prime 2). The count cnt[2] = 100000 means there are 100,000 different ways to pick that single 2. The DP transition dp[mask | m] += dp[mask] * cnt[v] accounts for this.
From understanding to recall
The trick to this problem is seeing the small prime universe and mapping it to bitmask DP. Once you spot that there are only 10 primes up to 30, the solution structure falls into place. But recognizing that connection under interview pressure takes practice.
Spaced repetition helps you internalize the pattern. You solve the problem today, see it again in three days, then a week later. Each repetition reinforces the link between "small value range," "prime bitmask," and "DP over masks." Eventually, when you see a problem with constrained values and subset selection, the bitmask DP approach surfaces automatically.
Related posts
- Counting Bits - Bit manipulation fundamentals that help with bitmask DP
- Partition Equal Subset Sum - Another subset problem solved with DP, different approach but similar thinking
- Combination Sum - Subset selection with constraints, showing how DP handles combinatorial choices