Leetcode Problem 2572. Count the Number of Square-Free Subsets

2572. Count the Number of Square-Free Subsets

Leetcode Solutions

Initialize a list of the first 10 prime numbers.
Create a DP table with dimensions [n+1][1024] where n is the length of nums.
Set dp[n][0] to 1, representing the empty subset.
Iterate over the elements of nums in reverse.
For each element, iterate over all possible masks.
Update dp[i][mask] by adding dp[i+1][mask] (excluding the current element).
If including the current element does not introduce a square factor, update dp[i][mask] by adding dp[i+1][new_mask] where new_mask includes the prime factors of the current element.
Return dp[0][0] - 1 to exclude the empty subset.

Programming Language

Purpose:

General Question

Debug My Code

image/screenshot of info(optional)

Full Screen