<p>An array is <strong>squareful</strong> if the sum of every pair of adjacent elements is a <strong>perfect square</strong>.</p>

<p>Given an integer array nums, return <em>the number of permutations of </em><code>nums</code><em> that are <strong>squareful</strong></em>.</p>

<p>Two permutations <code>perm1</code> and <code>perm2</code> are different if there is some index <code>i</code> such that <code>perm1[i] != perm2[i]</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,17,8]
<strong>Output:</strong> 2
<strong>Explanation:</strong> [1,8,17] and [17,8,1] are the valid permutations.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [2,2,2]
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 12</code></li>
	<li><code>0 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution {
    set<vector<int>> perm;
public:
    int numSquarefulPerms(vector<int>& nums) {
        vector<int> temp;
        map<int,int> freq;
        for(int x : nums)freq[x]++;

        helper(nums.size(), -1, temp, freq);

        return perm.size();
    }

    void helper(int n, int last, vector<int>& temp, map<int,int>& freq){
        if(temp.size()==n){
            perm.insert(temp);
            return;
        }

        for(auto it : freq){
            int e = it.first;
            if(it.second==0)continue;
            if(last==-1 || check(last, e)){
                temp.push_back(e);
                freq[e]--;
                helper(n, e, temp, freq);
                temp.pop_back();
                freq[e]++;
            }
        }
    }
    bool check(int a, int b){
        int sum = a+b;
        int sqrt_ = sqrt(sum);
        if(sqrt_*sqrt_==sum){
            return true;
        }

        return false;
    }
};
10100