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

    int Count_Permutations(std::vector<std::vector<int>>& graph, int bitmask, int node, std::vector<std::vector<int>>& cache){

        if(bitmask == ((1 << graph.size()) - 1)){
            return 1;
        }

        if(cache[bitmask][node] != -1){
            return cache[bitmask][node];
        }

        int result = 0;
        for(int i = 0; i < graph[node].size(); i++){
            
            if(bitmask & (1 << graph[node][i])) continue;

            result += Count_Permutations(graph, bitmask | (1 <<graph[node][i]), graph[node][i], cache); 
        }

        return cache[bitmask][node] = result;
    }

    int numSquarefulPerms(std::vector<int>& nums) {
        
        std::vector<std::vector<int>> graph(nums.size());
        std::vector<std::vector<int>> cache((1 << nums.size()), std::vector<int>(nums.size(), -1));
        std::vector<int> factorial(nums.size() + 1, 1);
        std::unordered_map<int, int> num_frequency;
        
        for(int i = 0; i < nums.size(); i++){
            
            num_frequency[nums[i]]++;

            for(int j = i+1; j < nums.size(); j++){
                int num = nums[i] + nums[j];
                int square = std::sqrt(num);
                if(square * square == num){
                    graph[i].push_back(j);
                    graph[j].push_back(i);
                }
            }
        }

        for(int i = 2; i <= nums.size(); i++){
            factorial[i] *= factorial[i-1] * i;
        }

        int result = 0;
        for(int i = 0; i < nums.size(); i++){
            result += Count_Permutations(graph, (1 << i), i, cache);
        }

        for(auto x : num_frequency){
            result /= factorial[x.second];
        }

        return result;
    }
};
16100