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

2572. Count the Number of Square-Free Subsets

Leetcode Solutions

DP + Bitmask (Prime Factorization)

  1. Initialize a list of the first 10 prime numbers.
  2. Create a DP table with dimensions [n+1][1024] where n is the length of nums.
  3. Set dp[n][0] to 1, representing the empty subset.
  4. Iterate over the elements of nums in reverse.
  5. For each element, iterate over all possible masks.
  6. Update dp[i][mask] by adding dp[i+1][mask] (excluding the current element).
  7. 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.
  8. Return dp[0][0] - 1 to exclude the empty subset.
UML Thumbnail

Backtracking with Prime Factorization

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...