> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Number of Squareful Arrays Python Solution

> Tested Python solution for LeetCode 996 with 19 pytest cases. Generate a practice environment with lcpy.

LeetCode 996, [Hard](/catalog/hard). Topics: [Array](/catalog/topics/array), [Hash Table](/catalog/topics/hash-table), [Math](/catalog/topics/math), [Dynamic Programming](/catalog/topics/dynamic-programming), [Backtracking](/catalog/topics/backtracking), [Bit Manipulation](/catalog/topics/bit-manipulation), [Bitmask](/catalog/topics/bitmask). [View on LeetCode](https://leetcode.com/problems/number-of-squareful-arrays/description/).

Generate this problem as a practice environment: tested reference solution, 19 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 996   # by problem number
lcpy gen -s number_of_squareful_arrays   # by problem name
```

## Problem

An array is **squareful** if the sum of every pair of adjacent elements is a **perfect square**.

Given an integer array `nums`, return *the number of permutations of* `nums` *that are* ***squareful***.

Two permutations `perm1` and `perm2` are different if there is some index `i` such that `perm1[i] != perm2[i]`.

### Examples

```
Input: nums = [1,17,8]
Output: 2
Explanation: [1,8,17] and [17,8,1] are the valid permutations.
```

```
Input: nums = [2,2,2]
Output: 1
```

### Constraints

* 1 \<= nums.length \<= 12
* 0 \<= nums\[i] \<= 10^9

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/number_of_squareful_arrays/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/number_of_squareful_arrays/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from collections import Counter
from functools import cache
from math import isqrt


class Solution:
    # Time: O(k^2 * 2^n) where k is the number of distinct values (k <= n <= 12)
    # Space: O(k * 2^n) for the memo table over (last value, used-element mask)
    def num_squareful_perms(self, nums: list[int]) -> int:
        n = len(nums)
        counts = Counter(nums)
        values = sorted(counts)
        positions = {
            value: sum(1 << i for i, x in enumerate(nums) if x == value) for value in values
        }

        def is_square(x: int) -> bool:
            root = isqrt(x)
            return root * root == x

        neighbors = {value: [b for b in values if is_square(value + b)] for value in values}

        @cache
        def dfs(last: int, mask: int) -> int:
            if mask == (1 << n) - 1:
                return 1
            total = 0
            for neighbor in neighbors[last]:
                if (mask & positions[neighbor]).bit_count() == counts[neighbor]:
                    continue
                free = positions[neighbor] & ~mask
                pick = (free & -free).bit_length() - 1
                total += dfs(neighbor, mask | (1 << pick))
            return total

        return sum(dfs(value, positions[value] & -positions[value]) for value in values)
```

## Complexity

| Time | Space |
| - | - |
| O(k^2 \* 2^n) where k is the number of distinct values (k \<= n \<= 12) | O(k \* 2^n) for the memo table over (last value, used-element mask) |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.