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

Given an integer array nums, return the total number of unique permutations of nums that are squareful.

Two permutations perm1 and perm2 are considered distinct if there exists at least one index i such that perm1[i] != perm2[i].

Constraints:

• $1 \leq$ nums.length $\leq 12$

• $0 \leq$ nums[i] $\leq 10^9$

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.