# The Number of Good Subsets
**Difficulty:** HARD
[External](https://leetcode.com/problems/the-number-of-good-subsets)
Canonical: https://scaleengineer.com/dsa/problems/the-number-of-good-subsets
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Bitmask](https://scaleengineer.com/dsa/patterns/bitmask)
**Data structures:** Array
**Companies:** [Media.net](https://scaleengineer.com/companies/media.net), [Lowe's](https://scaleengineer.com/companies/lowe's)
---
## Problem
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.

* For example, if `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 <= 105`
* `1 <= nums[i] <= 30`

# Approaches
## Brute-force Backtracking
This approach explores all possibilities of forming subsets using recursion. We first process the input array to count the frequencies of each number and filter out numbers that cannot be in a good subset (i.e., numbers with a squared prime factor, like 4, 8, 9, ...). Then, we use a recursive function to build subsets from the valid, unique numbers. For each unique number, we decide whether to include it in our subset or not. The decision to include a number depends on whether its prime factors conflict with the prime factors of numbers already in the subset.
**Time:** O(N + 2^U), where N is the length of `nums` and U is the number of unique, square-free numbers greater than 1 (U <= 29). The O(N) part is for counting frequencies. The O(2^U) part is for the recursion, which explores all combinations. This is too slow for the given constraints. · **Space:** O(U), where U is the number of unique, square-free numbers (U <= 29). This space is used for the recursion stack depth.
**Pros:** Conceptually simple and a direct translation of the combinatorial problem.
**Cons:** Extremely inefficient due to re-computation of the same subproblems.; The number of recursive calls grows exponentially with the number of unique square-free numbers, leading to a "Time Limit Exceeded" error on most platforms.
### Explanation
First, we pre-calculate the prime factorization for each number from 2 to 30. We can represent the set of prime factors using a bitmask, as there are only 10 primes less than or equal to 30 (2, 3, 5, 7, 11, 13, 17, 19, 23, 29). We also filter out numbers that are not square-free (e.g., 4, 9, 12) because they can never be part of a good subset. We count the frequency of each number in `nums`. The count of `1`s is handled separately. We create a list of unique, square-free numbers greater than 1 that appear in `nums`. A recursive function, say `countGoodSubsets(index, currentMask)`, is defined. This function calculates the number of ways to form good subsets using numbers from `unique_nums[index]` onwards, given that the combined prime mask of the subset formed so far is `currentMask`. The initial call is `countGoodSubsets(0, 0)`. This counts all subsets, including the empty one. We subtract 1 to exclude the empty set. Finally, we multiply this result by `2^countOfOnes` to account for the subsets containing `1`s. Each of the `countOfOnes` instances of `1` can either be in a subset or not, giving `2^countOfOnes` possibilities for each good subset formed by other numbers.

```java
// This is a conceptual sketch, not full implementation
// It would be part of a larger class structure
private int[] freq;
private List<Integer> uniqueNums;
private int[] primeMasks; // precomputed
private long MOD = 1_000_000_007;

private long solve(int index, int mask) {
    if (index == uniqueNums.size()) {
        return 1; // One way: choose empty set from here
    }

    // Option 1: Don't include uniqueNums[index]
    long count = solve(index + 1, mask);

    // Option 2: Include uniqueNums[index]
    int num = uniqueNums.get(index);
    int numMask = primeMasks[num];
    if ((mask & numMask) == 0) {
        count = (count + (long)freq[num] * solve(index + 1, mask | numMask)) % MOD;
    }
    return count;
}
```
### Algorithm
*   Create a frequency map `freq` for numbers in `nums`.
*   Identify square-free numbers from 2 to 30 and compute their prime factor bitmasks.
*   Create a list `uniqueNums` of unique, square-free numbers > 1 present in `nums`.
*   Define a recursive function `solve(index, mask)` that calculates the number of ways to form good subsets using numbers from `uniqueNums[index:]` given that the combined prime mask of the subset formed so far is `currentMask`.
*   The base case for the recursion is when `index` reaches the end of `uniqueNums`, at which point it returns 1.
*   In the recursive step, for `num = uniqueNums[index]`, it computes the sum of two cases:
    1.  Skipping `num`: `solve(index + 1, mask)`.
    2.  Including `num` (if its prime mask doesn't conflict): `freq[num] * solve(index + 1, mask | prime_mask(num))`.
*   Call `solve(0, 0)` to get the total number of valid subsets (including the empty one) from numbers > 1. Let the result be `total`.
*   The number of non-empty good subsets from numbers > 1 is `(total - 1)`.
*   Calculate `p = 2^freq[1]` using modular exponentiation.
*   The final answer is `((total - 1) * p) % MOD`.

## Backtracking with Memoization (Top-Down DP)
This approach improves upon the brute-force backtracking by using memoization to store the results of subproblems that have already been solved. This avoids redundant computations and drastically reduces the time complexity. The state of a subproblem is defined by the current index in the list of unique numbers and the current prime factor mask. We use a 2D array, `memo[index][mask]`, to store the result for `solve(index, mask)`.
**Time:** O(N + U * 2^P), where N is `nums.length`, U is the number of unique square-free numbers > 1 (<= 29), and P is the number of primes <= 30 (10). Each state `(index, mask)` is computed once. · **Space:** O(U * 2^P) for the memoization table, plus O(U) for the recursion stack. This is effectively O(30 * 1024), which is constant space with respect to N.
**Pros:** Efficient and guaranteed to pass within time limits.; Relatively easy to write once the recursive structure is defined.
**Cons:** Uses extra space for the memoization table.; Can lead to a `StackOverflowError` for very deep recursion, though not an issue here due to the small problem constraints (depth is at most 30).
### Explanation
The overall logic is identical to the pure backtracking approach. We still count frequencies, filter numbers, and use a recursive function. The key difference is the addition of a memoization table, `memo`, initialized with a value indicating that the state has not been computed (e.g., -1). The recursive function `solve(index, mask)` is modified: at the beginning of the function, it checks if `memo[index][mask]` has been computed. If so, it returns the stored value immediately. If not, it computes the result as in the pure backtracking approach and stores it in `memo[index][mask]` before returning. This technique is also known as top-down dynamic programming. It transforms the exponential complexity of the naive recursion into a polynomial time complexity determined by the number of states.

```java
class Solution {
    int[] freq;
    List<Integer> uniqueNums;
    int[] primeMasks;
    long[][] memo;
    long MOD = 1_000_000_007;
    int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};

    public int numberOfGoodSubsets(int[] nums) {
        freq = new int[31];
        for (int num : nums) {
            freq[num]++;
        }

        primeMasks = new int[31];
        uniqueNums = new ArrayList<>();

        for (int i = 2; i <= 30; i++) {
            if (freq[i] == 0) continue;
            int mask = 0;
            int temp = i;
            boolean isSquareFree = true;
            for (int j = 0; j < 10; j++) {
                if (temp % primes[j] == 0) {
                    if ((temp / primes[j]) % primes[j] == 0) {
                        isSquareFree = false;
                        break;
                    }
                    mask |= (1 << j);
                }
            }
            if (isSquareFree) {
                uniqueNums.add(i);
                primeMasks[i] = mask;
            }
        }

        memo = new long[uniqueNums.size()][1 << 10];
        for (long[] row : memo) {
            Arrays.fill(row, -1);
        }

        long count = solve(0, 0);
        long result = (count - 1 + MOD) % MOD; // Exclude the empty set

        long onesMultiplier = 1;
        for (int i = 0; i < freq[1]; i++) {
            onesMultiplier = (onesMultiplier * 2) % MOD;
        }

        result = (result * onesMultiplier) % MOD;
        return (int) result;
    }

    private long solve(int index, int mask) {
        if (index == uniqueNums.size()) {
            return 1;
        }
        if (memo[index][mask] != -1) {
            return memo[index][mask];
        }

        // Option 1: Don't include uniqueNums[index]
        long count = solve(index + 1, mask);

        // Option 2: Include uniqueNums[index]
        int num = uniqueNums.get(index);
        int numMask = primeMasks[num];
        if ((mask & numMask) == 0) {
            count = (count + (long)freq[num] * solve(index + 1, mask | numMask)) % MOD;
        }
        
        return memo[index][mask] = count;
    }
}
```
### Algorithm
*   Create a frequency map `freq`.
*   Identify square-free numbers from 2 to 30, compute their prime masks, and add them to a list `uniqueNums`.
*   Initialize a memoization table `memo[uniqueNums.size()][1024]` with a sentinel value (e.g., -1).
*   Define a recursive function `solve(index, mask)` that returns the number of valid subsets from `uniqueNums[index:]` given `mask`. It uses the `memo` table to store and retrieve results.
*   Before computing, the function checks `memo[index][mask]`. If a value exists, it's returned. Otherwise, the result is computed recursively as in the brute-force approach.
*   The computed result is stored in `memo[index][mask]` before returning.
*   Call `solve(0, 0)` to get the total number of valid subsets (including empty).
*   Subtract 1 for the empty set.
*   Multiply by `2^freq[1]` for the subsets involving 1s.
*   Return the final result modulo 10^9 + 7.

## Iterative Dynamic Programming (Bottom-Up)
This is the most efficient approach, implementing the same logic as the memoized recursion but in an iterative, bottom-up fashion. It avoids recursion overhead and can be slightly more space-efficient. We use a DP array, `dp[mask]`, where `dp[mask]` stores the number of subsets whose product's prime factors are represented by `mask`. We iterate through each unique, valid number from the input and update the DP table accordingly.
**Time:** O(N + C * 2^P), where N is `nums.length`, C is the number range (30), and P is the number of primes (10). This is dominated by O(N) if N is large, making it very efficient. · **Space:** O(C + 2^P) for the frequency map and the DP table, where C is the number range (30) and P is the number of primes (10). This is constant space, O(1), with respect to N.
**Pros:** Most efficient in terms of both time and space.; Avoids recursion, eliminating recursion overhead and risk of stack overflow.; The logic is clean and directly models the state transitions.
**Cons:** Can be slightly less intuitive to formulate than the recursive solution for some.
### Explanation
The pre-processing steps are the same: count frequencies and identify valid numbers (square-free, > 1) and their prime masks. We initialize a DP array `dp` of size `1 << 10` (1024). `dp[0]` is set to 1, representing the single empty subset, and all other `dp[i]` are 0. We iterate through each unique, square-free number `num > 1` that is present in `nums`. For each `num`, we iterate through all possible existing prime masks `mask` from `(1 << 10) - 1` down to 0. If `dp[mask]` is non-zero and `num`'s prime mask `numMask` does not conflict with `mask` (i.e., `(mask & numMask) == 0`), we can form new subsets by adding `num`. The number of new subsets formed is `dp[mask] * freq[num]`. These new subsets will have a combined prime mask of `mask | numMask`. So, we update `dp[mask | numMask]` by adding this amount. The iteration over `mask` must be done from high to low to avoid using a number `num` multiple times with subsets that were just formed in the current step. After iterating through all unique numbers, the `dp` array is fully populated. The total number of non-empty good subsets is the sum of all `dp[mask]` for `mask > 0`. Finally, this sum is multiplied by `2^freq[1]` to account for the number 1.

```java
class Solution {
    public int numberOfGoodSubsets(int[] nums) {
        int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
        int MOD = 1_000_000_007;
        int[] freq = new int[31];
        for (int n : nums) {
            freq[n]++;
        }

        long[] dp = new long[1 << 10];
        dp[0] = 1;

        for (int i = 2; i <= 30; i++) {
            if (freq[i] == 0) continue;

            // Check if i is square-free and get its mask
            int mask = 0;
            int temp = i;
            boolean isSquareFree = true;
            for (int j = 0; j < 10; j++) {
                if (temp % primes[j] == 0) {
                    if ((temp / primes[j]) % primes[j] == 0) {
                        isSquareFree = false;
                        break;
                    }
                    mask |= (1 << j);
                }
            }
            if (!isSquareFree) continue;

            // Update DP table
            for (int prevMask = (1 << 10) - 1; prevMask >= 0; prevMask--) {
                if (dp[prevMask] > 0 && (prevMask & mask) == 0) {
                    int newMask = prevMask | mask;
                    dp[newMask] = (dp[newMask] + dp[prevMask] * freq[i]) % MOD;
                }
            }
        }

        long totalGoodSubsets = 0;
        for (int i = 1; i < (1 << 10); i++) {
            totalGoodSubsets = (totalGoodSubsets + dp[i]) % MOD;
        }

        long onesMultiplier = 1;
        for (int i = 0; i < freq[1]; i++) {
            onesMultiplier = (onesMultiplier * 2) % MOD;
        }

        return (int)((totalGoodSubsets * onesMultiplier) % MOD);
    }
}
```
### Algorithm
*   Create a frequency map `freq`.
*   Initialize a DP array `dp` of size 1024 with `dp[0] = 1`.
*   Iterate `num` from 2 to 30. If `freq[num] == 0`, continue.
*   Check if `num` is square-free. If not, continue.
*   Calculate the prime mask `numMask` for `num`.
*   Iterate `mask` from 1023 down to 0.
*   If `(mask & numMask) == 0`, update `dp[mask | numMask] = (dp[mask | numMask] + dp[mask] * freq[num]) % MOD`.
*   After iterating through all numbers, sum up `dp[mask]` for `mask` from 1 to 1023. This is the count of good subsets from numbers > 1.
*   Multiply the result by `2^freq[1]` using modular exponentiation.
*   Return the final result.

# Solutions
### Java

```java
class Solution {
public
  int numberOfGoodSubsets(int[] nums) {
    int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
    int[] cnt = new int[31];
    for (int x : nums) {
      ++cnt[x];
    }
    final int mod = (int)1 e9 + 7;
    int n = primes.length;
    long[] f = new long[1 << n];
    f[0] = 1;
    for (int i = 0; i < cnt[1]; ++i) {
      f[0] = (f[0] * 2) % mod;
    }
    for (int x = 2; x < 31; ++x) {
      if (cnt[x] == 0 || x % 4 == 0 || x % 9 == 0 || x % 25 == 0) {
        continue;
      }
      int mask = 0;
      for (int i = 0; i < n; ++i) {
        if (x % primes[i] == 0) {
          mask |= 1 << i;
        }
      }
      for (int state = (1 << n) - 1; state > 0; --state) {
        if ((state & mask) == mask) {
          f[state] = (f[state] + cnt[x] * f[state ^ mask]) % mod;
        }
      }
    }
    long ans = 0;
    for (int i = 1; i < 1 << n; ++i) {
      ans = (ans + f[i]) % mod;
    }
    return (int)ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numberOfGoodSubsets(vector<int> &nums) {
    int primes[10] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
    int cnt[31]{};
    for (int &x : nums) {
      ++cnt[x];
    }
    int n = 10;
    const int mod = 1e9 + 7;
    vector<long long> f(1 << n);
    f[0] = 1;
    for (int i = 0; i < cnt[1]; ++i) {
      f[0] = f[0] * 2 % mod;
    }
    for (int x = 2; x < 31; ++x) {
      if (cnt[x] == 0 || x % 4 == 0 || x % 9 == 0 || x % 25 == 0) {
        continue;
      }
      int mask = 0;
      for (int i = 0; i < n; ++i) {
        if (x % primes[i] == 0) {
          mask |= 1 << i;
        }
      }
      for (int state = (1 << n) - 1; state; --state) {
        if ((state & mask) == mask) {
          f[state] = (f[state] + 1LL * cnt[x] * f[state ^ mask]) % mod;
        }
      }
    }
    long long ans = 0;
    for (int i = 1; i < 1 << n; ++i) {
      ans = (ans + f[i]) % mod;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def numberOfGoodSubsets(self, nums: List[int]) -> int: primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] cnt = Counter(nums) mod = 10 ** 9 + 7 n = len(primes) f = [0] * (1 << n) f[0] = pow(2, cnt[1]) for x in range(2, 31): if cnt[x] == 0 or x % 4 == 0 or x % 9 == 0 or x % 25 == 0: continue mask = 0 for i, p in enumerate(primes): if x % p == 0: mask |= 1 << i for state in range((1 << n) - 1, 0, - 1): if state & mask == mask: f[state] = (f[state] + cnt[x] * f[state ^ mask]) % mod return sum(f[i] for i in range(1, 1 << n)) % mod

```