Solution: The Number of Good Subsets

Explore how to efficiently count subsets of an integer array whose product is formed by distinct prime factors using dynamic programming and bitmask techniques. Understand how to represent prime factors as bit masks and apply a DP approach to avoid repeated factors. Gain skills to solve similar optimization problems in coding interviews.

We'll cover the following...

Statement
Solution
- Time complexity
- Space complexity

Statement

For a given integer array, nums, you can say that a subset of nums is called “good” if the product of its elements can be expressed as a product of one or more distinct prime numbers, i.e., no prime factor appears more than once.

For example, if nums $= [1, 2, 5, 6]$ , then:

$[2, 5]$ , $[1, 2, 5]$ , and $[6]$ are good subsets with products $2 \times 5 = 10$ , $1 \times 2 \times 5 = 10$ , and $2 \times 3 = 6$ , respectively.
$[2, 6]$ ...