<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 {
public:
    long long fact(int i)
    {
        if(i==1)
        return 1;

        return i*fact(i-1);
    }
    long long helper(int index,int mask,vector<int>&nums,vector<vector<long long>>&dp,int last)
    {
        int n=nums.size();

        if(index==n)
        return 1;

        if(last==-1)
        {
            long long ans=0;
            for(int i=0;i<n;i++)
            {
                ans=ans+helper(index+1,mask|(1<<i),nums,dp,i);
            }
            return ans;
        }
        if(dp[mask][last]!=-1)
        return dp[mask][last];

        int ans=0;

        for(int i=0;i<n;i++)
        {
            if(mask & (1<<i))
            continue;

            int val=nums[last]+nums[i];

            if(ceil(sqrt(val))==floor(sqrt(val)))
            {
                ans+=helper(index+1,mask|(1<<i),nums,dp,i);
            }   
        }
        return dp[mask][last]=ans;
    }

    int numSquarefulPerms(vector<int>& nums) {
        int n=nums.size();
        map<int,int> m;
        for(int i=0;i<n;i++)
        {
            m[nums[i]]++;
        }
        vector<pair<int,int>> arr;
        int maxi=0;
        for(auto i:m)
        {
            arr.push_back(i);
        }
       // n=arr.size();
        vector<vector<long long>> dp((1<<n),vector<long long>(n,-1));

        long long val=helper(0,0,nums,dp,-1);
        for(auto i:m)
        {
            val=val/fact(i.second);
        }
        return (int)val;
    }
};
19900