<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 {
 private:
 	bool square(int x){
 		int r = sqrt(x);
 		return x == r * r;
 	}
 	vector<vector<int>> dp_; //dp[cur][state]
 	
 	int dfs(vector<int>& A, int cur, int to_visit){
 		if(dp_[cur][to_visit]) return dp_[cur][to_visit];
 		else if(!to_visit) return 1;
 		int copy = to_visit;
 		int pre = -1, index = 0;
 		while(copy){
 			if((copy & 1) && square(A[cur] + A[index])){
 				if(pre == A[index]){
 					index ++;
 					copy >>= 1;
 					continue;
 				}
 				pre = A[index];
 				dp_[cur][to_visit] += dfs(A, index, to_visit ^ (1 << index));
 			}
 			index++;
 			copy >>= 1;
 		}
 		return dp_[cur][to_visit];
 	}
 public:
 	int numSquarefulPerms(vector<int>& A) {
 		const int n = A.size();
 		dp_ = vector<vector<int>>(n, vector<int>(1 << n, 0));
 		sort(A.begin(), A.end());
 		int res = 0;
 		int fullstate = (1 << n) - 1;
 		for(int i = 0; i < n; ++i){
 			if(i > 0 && A[i] == A[i - 1]) continue;
 			res += dfs(A, i, fullstate ^ (1 << i));
 		}
 		return res;
 	}
 };
13400