#2572

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Count the Number of Square-Free Subsets

Learn how to efficiently count square-free subsets using state transition dynamic programming with bitmask optimizations.

array math dynamic programming bit manipulation bitmask

Problem Statement

Given a positive integer array nums, a subset is considered square-free if the product of its elements is not divisible by any perfect square greater than 1. Return the total number of square-free subsets possible in nums.

Each number in nums is between 1 and 30, inclusive. Subsets can be of any size, including single-element subsets, and the empty subset is not counted. Your task is to implement an algorithm that efficiently counts all valid square-free subsets, considering that direct enumeration may be too slow for large arrays.

Examples

Example 1

Input: nums = [3,4,4,5]

Output: 3

There are 3 square-free subsets in this example:

The subset consisting of the 0th element [3]. The product of its elements is 3, which is a square-free integer.
The subset consisting of the 3rd element [5]. The product of its elements is 5, which is a square-free integer.
The subset consisting of 0th and 3rd elements [3,5]. The product of its elements is 15, which is a square-free integer. It can be proven that there are no more than 3 square-free subsets in the given array.

Example 2

Input: nums = [1]

Output: 1

There is 1 square-free subset in this example:

The subset consisting of the 0th element [1]. The product of its elements is 1, which is a square-free integer. It can be proven that there is no more than 1 square-free subset in the given array.

Constraints

1 <= nums.length <= 1000
1 <= nums[i] <= 30

Solution Approach

Prime Factor Bitmask Mapping

Precompute the prime factorization of numbers 1 to 30 and represent each number as a bitmask of its prime factors. This allows fast checks for square-free multiplicative combinations by ensuring no prime repeats in the subset product.

Dynamic Programming with State Transition

Use a DP array where each state represents a combination of primes in current subset products. For each number in nums, update DP by combining it with existing states if the number's prime bitmask does not conflict. This ensures only square-free subsets are counted without overcounting duplicates.

Handling Special Cases and Modulo

Include logic to handle the number 1 separately, since it does not affect the prime bitmask. Return the final count modulo 10^9 + 7 to prevent overflow. The DP approach ensures O(n * 2^k) time complexity where k is the number of primes under 30.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n * 2^10) since there are 10 primes under 30 and we iterate over each array element updating compatible bitmask states. Space complexity is O(2^10) for the DP states array.

What Interviewers Usually Probe

Recognize this as a subset counting problem with constraints on multiplicative combinations.
Expect the candidate to optimize with bitmask DP to avoid O(2^n) brute force.
Look for handling of edge numbers like 1 and duplicates efficiently.

Common Pitfalls or Variants

Common pitfalls

Failing to use bitmasks leads to slow subset enumeration for arrays of size 1000.
Ignoring repeated primes in a product may incorrectly count non-square-free subsets.
Forgetting to handle 1 separately can undercount valid subsets.

Follow-up variants

Count subsets whose product is divisible by a given set of primes without repeats.
Count square-free subsets in multi-dimensional arrays or matrices.
Modify problem to count subsets with product coprime to a given integer.

FAQ

What defines a square-free subset in this problem?

A subset is square-free if the product of its elements has no repeated prime factors, meaning no perfect square greater than 1 divides it.

Why use bitmasking for this DP approach?

Bitmasking represents prime factors efficiently, allowing quick checks for conflicts when combining subset products without enumerating all possibilities.

How does the state transition dynamic programming pattern apply here?

Each DP state tracks a combination of primes in current subset products, and transitions occur by adding compatible numbers to existing states, counting valid square-free subsets.

How should the number 1 be handled in subsets?

The number 1 does not affect prime factors, so it can be added to any subset freely, increasing the count without altering bitmask states.

What is the time complexity for counting square-free subsets with this approach?

Time complexity is O(n * 2^10), where n is the array length and 10 is the number of primes under 30, giving efficient performance for arrays up to length 1000.

terminal

Solution

Solution 1: State Compression Dynamic Programming

Note that in the problem, the range of $nums[i]$ is $[1, 30]$. Therefore, we can preprocess all prime numbers less than or equal to $30$, which are $[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def squareFreeSubsets(self, nums: List[int]) -> int:
        primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
        cnt = Counter(nums)
        mod = 10**9 + 7
        n = len(primes)
        f = [0] * (1 << n)
        f[0] = pow(2, cnt[1])
        for x in range(2, 31):
            if cnt[x] == 0 or x % 4 == 0 or x % 9 == 0 or x % 25 == 0:
                continue
            mask = 0
            for i, p in enumerate(primes):
                if x % p == 0:
                    mask |= 1 << i
            for state in range((1 << n) - 1, 0, -1):
                if state & mask == mask:
                    f[state] = (f[state] + cnt[x] * f[state ^ mask]) % mod
        return sum(v for v in f) % mod - 1

Continue Practicing

#1994 the number of good subsets #1799 maximize score after n operations #3444 minimum increments for target multiples in an array