Solution: The Number of Good Subsets

Explore how to solve the number of good subsets problem by using dynamic programming combined with bit masks to efficiently track prime factors. Understand the approach involving frequency counting, square-free validation, and DP state updates to count valid subsets without explicitly generating all possibilities.

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