## Algorithm

Problem Name: 996. Number of Squareful Arrays

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]`.

Example 1:

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

Example 2:

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

Constraints:

• `1 <= nums.length <= 12`
• `0 <= nums[i] <= 109`

## Code Examples

### #1 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int numSquarefulPerms(int[] nums) {
Arrays.sort(nums);
int[] count = {0};
backtrack(new ArrayList < >(), nums, new boolean[nums.length], -1, count);
return count[0];
}

private void backtrack(List < Integer> temp, int[] nums, boolean[] used, int lastNumber, int[] count) {
if (temp.size() == nums.length){
count[0]++;
return;
}
for (int i = 0; i  <  nums.length; i++){
if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])){
continue;
}
if (lastNumber != -1) {
if (!isSquare(nums[i] + lastNumber)) {
continue;
}
}
used[i] = true;
backtrack(temp, nums, used, nums[i], count);
temp.remove(temp.size() - 1);
used[i] = false;
}
}

private boolean isSquare(int num) {
int squareRoot = (int) Math.sqrt(num);
return squareRoot * squareRoot == num;
}
}
``````
Copy The Code &

Input

cmd
nums = [1,17,8]

Output

cmd
2

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const numSquarefulPerms = function (A) {
const cntMap = {}
const squareMap = {}
let cnt = 0
for (let num of A) {
if (!cntMap.hasOwnProperty(num)) {
cntMap[num] = 1
squareMap[num] = new Set()
} else {
cntMap[num] = cntMap[num] + 1
}
}

for (let num1 of Object.keys(cntMap)) {
for (let num2 of Object.keys(cntMap)) {
let c = Math.sqrt(+num1 + +num2)
if (c === Math.floor(c)) {
}
}
}
for (let num of Object.keys(cntMap)) {
countPerm(num, A.length - 1)
}
return cnt
function countPerm(num, left) {
cntMap[num] = cntMap[num] - 1
if (left === 0) {
cnt++
} else {
for (let next of squareMap[num]) {
if (cntMap[next] !== 0) {
countPerm(next, left - 1)
}
}
}
cntMap[num] = cntMap[num] + 1
}
}
``````
Copy The Code &

Input

cmd
nums = [1,17,8]

Output

cmd
2

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def numSquarefulPerms(self, A: List[int]) -> int:
self.res = 0
def dfs(cnt, num):
if not cnt:
self.res += 1
for new in nex[num]:
if cnt[new]:
cnt[new] -= 1
if not cnt[new]:
cnt.pop(new)
dfs(cnt, new)
cnt[new] += 1

nex = collections.defaultdict(set)
cnt = collections.Counter(A)
for a, b in itertools.permutations(A, 2):
if not (a + b) ** 0.5 % 1:
for a in set(A):
cnt[a] -= 1
if not cnt[a]:
cnt.pop(a)
dfs(cnt, a)
cnt[a] += 1
return self.res
``````
Copy The Code &

Input

cmd
nums = [2,2,2]

Output

cmd
1