The number of good subsets

Array Hash Table Math Dynamic Programming Bit Manipulation Counting Number Theory Bitmask

37.1% acceptance

Feb 25, 2026

507

You are given an integer array nums. We call a subset of nums good if its product can be represented as a product of one or more distinct prime numbers. For example, if nums = [1, 2, 3, 4]: [2, 3], [1, 2, 3], and [1, 3] are good subsets with products 6 = 2*3, 6 = 2*3, and 3 = 3 respectively. [1, 4] and [4] are not good subsets with products 4 = 2*2 and 4 = 2*2 respectively. Return the number of different good subsets in nums modulo 109 + 7. A subset of nums is any array that can be obtained by deleting some (possibly none or 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 number_of_good_subsets(nums: Vec<i32>) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29];
    
    // Count frequency of each number 1..30
    let mut freq = [0i64; 31];
    for &num in &nums {
      freq[num as usize] += 1;
    }
    
    // For each number 2..30, compute its prime bitmask (if it has repeated prime factors, skip it)
    let mut mask_of = [0i32; 31]; // -1 means invalid
    let mut valid = [true; 31];
    for num in 2..=30 {
      let mut n = num;
      let mut mask = 0i32;
      for (pi, &p) in primes.iter().enumerate() {
        if n % p == 0 {
          n /= p;
          if n % p == 0 {
            valid[num as usize] = false;
            break;
          }
          mask |= 1 << pi;
        }
      }
      mask_of[num as usize] = mask;
    }
    
    // dp[mask] = number of ways to form a subset with the given prime mask
    let total_masks = 1 << primes.len();
    let mut dp = vec![0i64; total_masks];
    dp[0] = 1;
    
    for num in 2..=30i32 {
      if !valid[num as usize] || freq[num as usize] == 0 {
        continue;
      }
      let m = mask_of[num as usize] as usize;
      let cnt = freq[num as usize];
      // Iterate in reverse to avoid using same number twice in different values
      // But since we process by value and can pick multiple copies:
      // Actually each value can appear multiple times, but each copy is distinct.
      // For a value v with count c, we can pick 1..c copies (but since mask can only include v once,
      // we pick exactly one copy out of c, giving c choices)
      for mask in (0..total_masks).rev() {
        if dp[mask] == 0 {
          continue;
        }
        if mask & m == 0 {
          dp[mask | m] = (dp[mask | m] + dp[mask] * cnt) % MOD;
        }
      }
    }
    
    // Sum all non-zero masks
    let mut ans: i64 = 0;
    for mask in 1..total_masks {
      ans = (ans + dp[mask]) % MOD;
    }
    
    // Multiply by 2^(count of 1s) since each 1 can be included or not
    let ones = freq[1];
    let mut pow2 = 1i64;
    for _ in 0..ones {
      pow2 = pow2 * 2 % MOD;
    }
    
    (ans * pow2 % MOD) as i32
  }
}