Solution Explanation for LeetCode 1994: The Number of Good Subsets

This problem asks to find the number of "good" subsets of a given integer array nums. A subset is considered "good" if its product is composed solely of distinct prime factors. The solution utilizes bit manipulation and dynamic programming for efficient computation.

Understanding the Approach

1. Prime Factorization: The core idea is to represent each number in nums by its prime factorization. Since the numbers are limited to a maximum of 30, we only need to consider the primes 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29. Numbers with repeated prime factors (e.g., 4 = 22, 9 = 33, 25 = 5*5) are immediately disqualified as they cannot form a good subset.

2. Bitmasking: We use a bitmask to represent the presence of prime factors in a subset's product. Each bit in the mask corresponds to a prime number (e.g., bit 0 for 2, bit 1 for 3, etc.). If a prime factor is present in the product, the corresponding bit is set to 1.

3. Dynamic Programming: We employ dynamic programming to efficiently count good subsets. f[mask] represents the number of good subsets whose product's prime factors are represented by mask.

4. Base Case: The base case is f[0], which represents the number of subsets containing only 1 (as 1 has no prime factors). The count of subsets with only 1 is 2<sup>count(1)</sup>, where count(1) is the number of occurrences of 1 in nums.

5. Iteration: We iterate through the numbers in nums (excluding 1). For each number x, we determine its prime factors and construct the corresponding bitmask mask. Then, we update f[mask] by adding the number of ways to form subsets with the current prime factors to the existing f[mask]. The formula for this update is a bit more complex due to the fact that we can have multiple copies of the same number and this needs to be taken into account.

6. Final Result: Finally, we sum up the values of f[mask] for all non-zero masks (as zero mask indicates no prime factors) to obtain the total number of good subsets. The modulo operation ensures the result is within the specified range.

Time Complexity Analysis

• The prime factorization of each number is done in O(log n), where n is the maximum number (30 in this case). This step is performed for each unique number in nums.
• The dynamic programming step iterates through all possible bitmasks (210 = 1024).
• The overall time complexity is dominated by the dynamic programming step and is O(2k * m), where k is the number of primes considered (10) and m is the number of unique numbers in nums.

Space Complexity Analysis

The space complexity is O(2k), primarily due to the f array used in dynamic programming.

Code Explanation (Python)

The Python code effectively implements the algorithm described above.

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], mod) #base case: subsets with only 1
 
        for x in range(2, 31):
            if cnt[x] == 0 or x % 4 == 0 or x % 9 == 0 or x % 25 == 0:
                continue #Skip numbers with repeated prime factors
            mask = 0
            for i, p in enumerate(primes):
                if x % p == 0:
                    mask |= 1 << i  #construct bitmask
            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

The other language versions (Java, C++, Go) follow a very similar structure and logic, adapting the syntax and data structures to their respective languages. They all efficiently solve the problem using the described bit manipulation and dynamic programming techniques within the constraints of the problem.