Count the number of square free subsets

Array Math Dynamic Programming Bit Manipulation Bitmask

26.4% acceptance

Feb 25, 2026

505

123

You are given a positive integer 0-indexed array nums. A subset of the array nums is square-free if the product of its elements is a square-free integer. A square-free integer is an integer that is divisible by no square number other than 1. Return the number of square-free non-empty subsets of the array nums. Since the answer may be too large, return it modulo 109 + 7. A non-empty subset of nums is an array that can be obtained by deleting some (possibly none but not all) elements from nums. Two subsets are different if and only if the chosen indices to delete are different.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn square_free_subsets(nums: Vec<i32>) -> i32 {
    const MOD: i64 = 1_000_000_007;
    // Primes up to 30: 10 primes -> 2^10 = 1024 bitmask states
    let primes = [2i32, 3, 5, 7, 11, 13, 17, 19, 23, 29];

    // Precompute prime bitmask for each value 1..=30
    // Returns None if value has a square prime factor
    let prime_mask = |v: i32| -> Option<u32> {
      let mut mask = 0u32;
      let mut x = v;
      for (i, &p) in primes.iter().enumerate() {
        if x % p == 0 {
          x /= p;
          if x % p == 0 { return None; } // squared
          mask |= 1 << i;
        }
      }
      Some(mask)
    };

    // Count frequency of each value
    let mut freq = [0i64; 31];
    for &n in &nums { freq[n as usize] += 1; }

    let mut dp = vec![0i64; 1024];
    dp[0] = 1;

    // Process each value 2..=30 with no square factor
    for v in 2..=30i32 {
      if freq[v as usize] == 0 { continue; }
      if let Some(pmask) = prime_mask(v) {
        let cnt = freq[v as usize];
        // Iterate masks in reverse to avoid reuse (each value used at most once)
        for mask in (0..1024usize).rev() {
          if dp[mask] == 0 { continue; }
          let pmask = pmask as usize;
          if mask & pmask == 0 {
            dp[mask | pmask] = (dp[mask | pmask] + dp[mask] * cnt) % MOD;
          }
        }
      }
    }

    // Multiply by 2^freq[1] (each '1' can be in or out independently)
    let ones = freq[1];
    let mut pow2 = 1i64;
    for _ in 0..ones { pow2 = pow2 * 2 % MOD; }

    // Total = (sum of all dp states) * 2^freq[1] - 1 (subtract empty set)
    let sum: i64 = dp.iter().sum::<i64>() % MOD;
    let ans = ((sum * pow2 % MOD) - 1 + MOD) % MOD;
    ans as i32
  }
}