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

#define ll long long int 
class Solution {
public:
    map<pair<int,int>,int> m;
    map<pair<int,int>,int> dp;
    
    ll sqrt(ll a){
        ll l=0;
        ll h=a;
        ll ans=0;
        while(l<=h){
            //cout<<l<<h<<" ";
            ll mid=(l+h)/2;
            if(mid*mid<=a) {ans=mid; l=mid+1; }
            else h=mid-1;
        }
        return ans;
    }

    bool issq(int a , int b){
        ll as=1LL*a;
        ll bs=1LL*b;
        ll total=as+bs;
        ll c=sqrt(total);
        //cout<<total<<c<<" ";
        if((c*c)==total) return 1;
        return 0;
    }

    int func( vector<int>& nums,int last,int over,int mask ){
        //cout<<last<<" ";
        int n=nums.size();
        if(over==n) { return 1; }
        if( dp.find({last,mask})!=dp.end() ) return dp[{last,mask}];
        int ans=0;
        int latest=-1;
        int i=0;
        //cout<<last<<" ";
        while(i<n){
            if(mask&(1<<i)){
                //cout<<i<<" ";
                if(m[{last,nums[i]}]==1){
                    //cout<<i<<" ";
                    if(nums[i]!=latest) ans+=func(nums,nums[i],over+1,mask^(1<<i));
                }
                latest=nums[i];
            }
            i++;
        }
        return dp[{last,mask}]=ans;
    }

    int numSquarefulPerms(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<int> &a=nums;
        int finalans=0;
        int n=nums.size();
        // map<pair<int,int>,int> m;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                //if(i==j) continue; 
                if(issq(a[i],a[j])){ m[{a[i],a[j]}]=1; }
            }
        }
        int mask=(1<<n)-1;
        int latest=-1;
        for(int i=0;i<n;i++){
            if(a[i]!=latest)
            { finalans+=func(nums,a[i],1,mask^(1<<i)); }
            latest=a[i];
        }
        return finalans;
    }
};
10700