# Count The Number Of Good Subsets: Walkthrough
Count The Number Of Good Subsets shows up often in coding rounds. Here is how I talk through it when the interviewer is watching.
## Key idea
A subset (with frequencies) is good if the product of its values is square-free (no repeated prime factors). nums[i] in 1..30: sieve the 10 primes under 30, drop numbers with a squared factor, then DP over bitmasks of used primes while placing each distinct value 0/1 times (and multiply by its frequency). 1s are free multipliers (2^{cnt[1]}).
## Steps to say out loud
1. Restate the input and the exact ask, and nail down constraints and overflow.
2. Name the pattern (binary search on the answer, monotonic stack or deque, interval / interval-DP, string hashing, graph traversal, or shortest paths) and why a nested scan or naive search fails.
3. Code it, then trace a short example plus one empty or already-solved edge case.
## Complexity
O(2^P * 30).
## Common mistake
Allowing a number like 4 or 12 that already contains a square, or treating 1 as using a prime bit.
## Practice tip
Time yourself: two minutes to explain, ten to code, three to test edges. Disclosure: I work on Linkjob AI. I also keep a practice cheat sheet at try it free.