Solution: The Number of Good Subsets

Explore how to solve the problem of counting good subsets in an integer array by using dynamic programming combined with bit masking. Understand how to represent prime factors with bit masks, ensure no repeated primes, and efficiently count valid subsets. This lesson helps you master pattern-based dynamic programming to optimize subset computations for 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]$ ...