Solution: The Number of Good Subsets

Explore how to solve the problem of counting good subsets in an integer array using dynamic programming and bit masks. This lesson helps you understand tracking prime factors uniquely and applying DP to handle large input efficiently while ensuring no repeated prime factors in product subsets.

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]$ ...