# Count the Number of Square-Free Subsets
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-the-number-of-square-free-subsets)
Canonical: https://scaleengineer.com/dsa/problems/count-the-number-of-square-free-subsets
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Bitmask](https://scaleengineer.com/dsa/patterns/bitmask)
**Data structures:** Array
**Companies:** [Media.net](https://scaleengineer.com/companies/media.net)
---
## Problem
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.

**Example 1:**

**Input:** nums = [3,4,4,5]
**Output:** 3
**Explanation:** 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
**Explanation:** 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`

# Approaches
## Backtracking on Unique Square-Free Numbers
This approach uses a recursive backtracking algorithm. We first process the input array to count the frequencies of each number and filter out non-square-free numbers. The core of the approach is a recursive function that explores the choices of including or not including each unique square-free number to form a valid subset. A subset is valid if the prime factors of the newly added number do not overlap with the prime factors of the numbers already in the subset. We use a bitmask to efficiently track the set of prime factors used.
**Time:** O(N + 2^U), where `N` is the length of `nums` and `U` is the number of unique square-free numbers present in `nums` (`U <= 18`). The `O(N)` is for preprocessing `nums`. The `2^U` comes from the binary recursion tree. Since `U` is small, this approach is feasible and can pass. · **Space:** O(U), where `U` is the number of unique square-free numbers in `nums`. This space is used by the recursion stack. Since `U` is at most 18, this is effectively constant space.
**Pros:** Conceptually straightforward recursive solution that directly models the decision process.
**Cons:** Highly inefficient due to re-computation of results for the same state (index and mask).; The time complexity is exponential in the number of unique square-free elements, which might be too slow if the number of such elements were larger.
### Explanation
First, we can simplify the problem. Any number in `nums` that is not square-free (i.e., divisible by 4, 9, 25, etc.) can never be part of a square-free subset, so we can ignore them. The number 1 is square-free and coprime with any other number, so it can be combined with any square-free subset. We can handle all occurrences of 1s at the end.

The problem then reduces to finding the number of square-free subsets of `nums` containing only square-free numbers greater than 1. A subset is square-free if and only if all its elements are square-free and pairwise coprime. This means their sets of prime factors must be disjoint.

We can represent the set of prime factors of a number using a bitmask. Since all numbers are at most 30, we only need to consider primes up to 30, which are {2, 3, 5, 7, 11, 13, 17, 19, 23, 29} (10 primes).

The algorithm proceeds as follows:
- Count the frequency of each number in `nums`.
- Let `count1` be the frequency of the number 1.
- Create a list of unique square-free numbers > 1 present in `nums`.
- A recursive function `solve(idx, mask)` is defined, which calculates the number of valid subsets using numbers from `unique_sf_nums[idx:]`, given that the primes represented by `mask` are already used.
- In `solve(idx, mask)`, we have two choices for `unique_sf_nums[idx]`:
  1. Don't include it: Recursively call `solve(idx + 1, mask)`.
  2. Include it: This is possible only if its prime factor mask doesn't overlap with `mask`. If so, we add `count(num) * solve(idx + 1, new_mask)` to the result, where `count(num)` is the frequency of the number.
- The base case for the recursion is when `idx` reaches the end of the list, in which case we return 1 (for the one valid subset formed).
- The initial call is `solve(0, 0)`. Let the result be `C'`. This is the number of square-free subsets (including empty) from numbers > 1.
- The total number of subsets is `C' * 2^count1`. The final answer is this value minus 1 (to exclude the all-empty subset).

```java
class Solution {
    int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
    int[] masks;
    long MOD = 1_000_000_007;
    List<Integer> uniqueSfNums;
    int[] counts;

    public int squareFreeSubsets(int[] nums) {
        counts = new int[31];
        for (int num : nums) {
            counts[num]++;
        }

        masks = new int[31];
        for (int i = 2; i <= 30; i++) {
            masks[i] = getMask(i);
        }

        uniqueSfNums = new ArrayList<>();
        for (int i = 2; i <= 30; i++) {
            if (counts[i] > 0 && masks[i] != -1) {
                uniqueSfNums.add(i);
            }
        }

        long countGt1 = solve(0, 0);
        long count1 = counts[1];
        long total = (countGt1 * power(2, count1)) % MOD;
        return (int)((total - 1 + MOD) % MOD);
    }

    private long solve(int idx, int mask) {
        if (idx == uniqueSfNums.size()) {
            return 1;
        }

        // Option 1: Don't include uniqueSfNums[idx]
        long res = solve(idx + 1, mask);

        // Option 2: Include uniqueSfNums[idx]
        int num = uniqueSfNums.get(idx);
        int numMask = masks[num];
        if ((mask & numMask) == 0) {
            long ways = (counts[num] * solve(idx + 1, mask | numMask)) % MOD;
            res = (res + ways) % MOD;
        }

        return res;
    }

    private int getMask(int n) {
        int mask = 0;
        for (int i = 0; i < primes.length; i++) {
            int p = primes[i];
            if (n % (p * p) == 0) return -1; // Not square-free
            if (n % p == 0) {
                mask |= (1 << i);
            }
        }
        return mask;
    }

    private long power(long base, long exp) {
        long res = 1;
        base %= MOD;
        while (exp > 0) {
            if (exp % 2 == 1) res = (res * base) % MOD;
            base = (base * base) % MOD;
            exp /= 2;
        }
        return res;
    }
}
```
### Algorithm
1. Pre-process the input `nums` to count the frequency of each number.
2. Identify the unique square-free numbers greater than 1 present in `nums`.
3. Implement a recursive function, say `solve(index, mask)`, where `index` refers to the current unique square-free number being considered, and `mask` is a bitmask representing the prime factors used by the subset constructed so far.
4. In the recursive function, for each number, explore two possibilities:
    a. **Exclude the number:** Make a recursive call `solve(index + 1, mask)`.
    b. **Include the number:** If its prime factor mask does not conflict with the current `mask`, make a recursive call `solve(index + 1, new_mask)` and multiply the result by the frequency of the number. This accounts for the different ways to choose this number if it appears multiple times.
5. The base case for the recursion is when all unique numbers have been considered (`index` reaches the end), at which point we return 1 (representing one validly formed subset).
6. Sum the results from the recursive calls to get the total count of square-free subsets formed from numbers greater than 1 (let's call this `C'`).
7. The number 1 can be part of any square-free subset. If there are `k` ones in `nums`, they can form `2^k` subsets (including the empty one). The total number of square-free subsets is `C' * 2^k`.
8. Subtract 1 from the total to exclude the overall empty subset and return the result modulo `10^9 + 7`.

## Top-Down Dynamic Programming with Memoization
This approach optimizes the backtracking solution by using memoization to store and reuse the results of subproblems. This avoids redundant computations and significantly improves performance. The state for memoization is defined by the current index of the unique square-free number being considered and the current bitmask of used prime factors.
**Time:** O(N + U * 2^P), where `N` is `nums.length`, `U <= 18`, and `P = 10`. The complexity is dominated by filling the memoization table. Since `U` and `P` are small constants, this is effectively O(N). · **Space:** O(U * 2^P) for the memoization table, where `U` is the number of unique square-free numbers (`<=18`) and `P` is the number of primes (`=10`). This is effectively constant space.
**Pros:** Much more efficient than plain backtracking by avoiding re-computation.; Guarantees that each subproblem is solved only once, leading to a polynomial time complexity in terms of states.
**Cons:** Requires extra space for the memoization table.; Has a slightly higher overhead than the iterative bottom-up approach due to recursion function calls.
### Explanation
The core idea is the same as the plain backtracking approach. We identify unique square-free numbers and their counts. We use a recursive function to build subsets, ensuring they are pairwise coprime using prime factor bitmasks.

The key difference is the addition of a memoization table, `memo[idx][mask]`, which stores the result of `solve(idx, mask)`.

Before computing `solve(idx, mask)`, we first check if the result is already in our memoization table. If it is, we return the stored value immediately. Otherwise, we compute the result as in the backtracking approach and store it in the table before returning.

This technique transforms the exponential complexity of the plain recursion into a solution with complexity proportional to the number of states, which is much more efficient.

The rest of the logic, including handling the number 1 and calculating the final result, remains the same.

```java
class Solution {
    int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
    int[] masks;
    long MOD = 1_000_000_007;
    List<Integer> uniqueSfNums;
    int[] counts;
    Long[][] memo;

    public int squareFreeSubsets(int[] nums) {
        counts = new int[31];
        for (int num : nums) {
            counts[num]++;
        }

        masks = new int[31];
        for (int i = 2; i <= 30; i++) {
            masks[i] = getMask(i);
        }

        uniqueSfNums = new ArrayList<>();
        for (int i = 2; i <= 30; i++) {
            if (counts[i] > 0 && masks[i] != -1) {
                uniqueSfNums.add(i);
            }
        }
        
        memo = new Long[uniqueSfNums.size()][1 << 10];
        long countGt1 = solve(0, 0);
        long count1 = counts[1];
        long total = (countGt1 * power(2, count1)) % MOD;
        return (int)((total - 1 + MOD) % MOD);
    }

    private long solve(int idx, int mask) {
        if (idx == uniqueSfNums.size()) {
            return 1;
        }
        if (memo[idx][mask] != null) {
            return memo[idx][mask];
        }

        // Option 1: Don't include uniqueSfNums[idx]
        long res = solve(idx + 1, mask);

        // Option 2: Include uniqueSfNums[idx]
        int num = uniqueSfNums.get(idx);
        int numMask = masks[num];
        if ((mask & numMask) == 0) {
            long ways = (counts[num] * solve(idx + 1, mask | numMask)) % MOD;
            res = (res + ways) % MOD;
        }

        return memo[idx][mask] = res;
    }

    private int getMask(int n) {
        int mask = 0;
        for (int i = 0; i < primes.length; i++) {
            int p = primes[i];
            if (n % (p * p) == 0) return -1;
            if (n % p == 0) {
                mask |= (1 << i);
            }
        }
        return mask;
    }

    private long power(long base, long exp) {
        long res = 1;
        base %= MOD;
        while (exp > 0) {
            if (exp % 2 == 1) res = (res * base) % MOD;
            base = (base * base) % MOD;
            exp /= 2;
        }
        return res;
    }
}
```
### Algorithm
1. The overall logic is identical to the plain backtracking approach.
2. A memoization table (e.g., a 2D array `memo[index][mask]`) is introduced to store the results of the recursive function `solve(index, mask)`.
3. Before computing `solve(index, mask)`, check if `memo[index][mask]` already contains a result. If so, return the stored value.
4. If the result is not in the memoization table, compute it using the same recursive logic as before.
5. After computing the result, store it in `memo[index][mask]` before returning it.
6. The rest of the steps, including handling the number 1 and calculating the final answer, remain unchanged.

## Bottom-Up Dynamic Programming with Bitmask
This is the most optimized approach, using an iterative, bottom-up dynamic programming method. It eliminates recursion overhead entirely. We use a DP array, `dp[mask]`, to store the number of square-free subsets whose combined prime factors are represented by `mask`. We iterate through each unique square-free number and update the DP table based on the subsets that can be formed by including this number.
**Time:** O(N + K * 2^P), where `N` is `nums.length`, `K` is the range of numbers (30), and `P` is the number of primes (10). Since `K` and `P` are constants, the complexity is linear in the size of the input, O(N). · **Space:** O(K + 2^P), where `K` is the range of numbers (31) and `P` is the number of primes (10). This is for the counts and DP arrays, which is constant space.
**Pros:** Most efficient in practice due to being iterative and avoiding recursion overhead.; Clean and concise implementation.; Space efficient as it only requires a single DP array.
**Cons:** The logic might be slightly less intuitive to formulate compared to the recursive top-down approach for those more accustomed to recursion.
### Explanation
This approach builds the solution iteratively. The state `dp[mask]` represents the number of ways to form a square-free subset (from numbers > 1 considered so far) with a combined prime factor mask of `mask`.

The algorithm is as follows:
1. Pre-process `nums` to get the frequency count of each number. Handle the count of 1s separately.
2. Initialize a DP array `dp` of size `1024` (for `2^10` prime masks). Set `dp[0] = 1` (representing the empty subset) and all other entries to 0.
3. Iterate through each number `num` from 2 to 30.
4. If `num` is present in `nums` (i.e., `count(num) > 0`) and is square-free:
   a. Get its prime factor mask, `num_mask`.
   b. Iterate through all existing masks `mask` in the `dp` table (from `1023` down to `0` to avoid using `num` multiple times within the same main step).
   c. If `num` can be added to subsets with prime mask `mask` (i.e., `(mask & num_mask) == 0`), update the `dp` entry for the new combined mask:
      `dp[mask | num_mask] += dp[mask] * count(num)`.
5. After iterating through all numbers, the sum of all values in the `dp` array gives the total number of square-free subsets (including the empty one) that can be formed from numbers > 1. Let this be `C'`.
6. The final result is calculated as `(C' * 2^count(1) - 1) % MOD`.

```java
class Solution {
    public int squareFreeSubsets(int[] nums) {
        int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
        long MOD = 1_000_000_007;
        int[] counts = new int[31];
        for (int num : nums) {
            counts[num]++;
        }

        long[] dp = new long[1 << 10];
        dp[0] = 1;

        for (int i = 2; i <= 30; i++) {
            if (counts[i] == 0) continue;

            int mask = 0;
            int temp = i;
            boolean isSquareFree = true;
            for (int j = 0; j < primes.length; j++) {
                int p = primes[j];
                if (temp % (p * p) == 0) {
                    isSquareFree = false;
                    break;
                }
                if (temp % p == 0) {
                    mask |= (1 << j);
                }
            }

            if (!isSquareFree) continue;

            for (int j = (1 << 10) - 1; j >= 0; j--) {
                if ((j & mask) == 0) {
                    dp[j | mask] = (dp[j | mask] + dp[j] * counts[i]) % MOD;
                }
            }
        }

        long totalSubsets = 0;
        for (long count : dp) {
            totalSubsets = (totalSubsets + count) % MOD;
        }

        long count1 = counts[1];
        long powerOf2 = 1;
        // Modular exponentiation is better, but this is fine for N<=1000
        for (int i = 0; i < count1; i++) {
            powerOf2 = (powerOf2 * 2) % MOD;
        }

        totalSubsets = (totalSubsets * powerOf2) % MOD;
        
        return (int)((totalSubsets - 1 + MOD) % MOD);
    }
}
```
### Algorithm
1. Pre-process `nums` to get the frequency count of each number. Store the count of 1s separately.
2. Initialize a DP array, `dp`, of size `1024` (for `2^10` prime masks). `dp[mask]` will store the number of square-free subsets with a combined prime factor mask equal to `mask`.
3. Set `dp[0] = 1`, representing the single empty subset, which has a mask of 0.
4. Iterate through each number `num` from 2 to 30.
5. If `num` is present in `nums` and is square-free, get its prime factor mask, `num_mask`.
6. Iterate through all existing masks `j` in the `dp` table (from `1023` down to `0`). The downward iteration is crucial to ensure that we use the `dp` values from *before* considering the current number `num`.
7. If `num` can be added to subsets with prime mask `j` (i.e., `(j & num_mask) == 0`), update the `dp` entry for the new combined mask: `dp[j | num_mask] = (dp[j | num_mask] + dp[j] * count(num)) % MOD`.
8. After iterating through all numbers, sum all values in the `dp` array to get the total number of square-free subsets (including the empty one) from numbers > 1. Let this be `C'`.
9. Calculate the final result as `(C' * 2^count(1) - 1) % MOD`.

# Solutions
### Java

```java
class Solution {
public
  int squareFreeSubsets(int[] nums) {
    int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
    int[] cnt = new int[31];
    for (int x : nums) {
      ++cnt[x];
    }
    final int mod = (int)1 e9 + 7;
    int n = primes.length;
    long[] f = new long[1 << n];
    f[0] = 1;
    for (int i = 0; i < cnt[1]; ++i) {
      f[0] = (f[0] * 2) % mod;
    }
    for (int x = 2; x < 31; ++x) {
      if (cnt[x] == 0 || x % 4 == 0 || x % 9 == 0 || x % 25 == 0) {
        continue;
      }
      int mask = 0;
      for (int i = 0; i < n; ++i) {
        if (x % primes[i] == 0) {
          mask |= 1 << i;
        }
      }
      for (int state = (1 << n) - 1; state > 0; --state) {
        if ((state & mask) == mask) {
          f[state] = (f[state] + cnt[x] * f[state ^ mask]) % mod;
        }
      }
    }
    long ans = 0;
    for (int i = 0; i < 1 << n; ++i) {
      ans = (ans + f[i]) % mod;
    }
    ans -= 1;
    return (int)ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int squareFreeSubsets(vector<int> &nums) {
    int primes[10] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
    int cnt[31]{};
    for (int &x : nums) {
      ++cnt[x];
    }
    int n = 10;
    const int mod = 1e9 + 7;
    vector<long long> f(1 << n);
    f[0] = 1;
    for (int i = 0; i < cnt[1]; ++i) {
      f[0] = f[0] * 2 % mod;
    }
    for (int x = 2; x < 31; ++x) {
      if (cnt[x] == 0 || x % 4 == 0 || x % 9 == 0 || x % 25 == 0) {
        continue;
      }
      int mask = 0;
      for (int i = 0; i < n; ++i) {
        if (x % primes[i] == 0) {
          mask |= 1 << i;
        }
      }
      for (int state = (1 << n) - 1; state; --state) {
        if ((state & mask) == mask) {
          f[state] = (f[state] + 1LL * cnt[x] * f[state ^ mask]) % mod;
        }
      }
    }
    long long ans = -1;
    for (int i = 0; i < 1 << n; ++i) {
      ans = (ans + f[i]) % mod;
    }
    return ans;
  }
};

```

### Python

```python
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

```