# 996. Number of Squareful Arrays 正方形数组的数目

@TOC

## # 题目描述

Given an array `A` of non-negative integers, the array is squareful if for every pair of adjacent elements, their sum is a perfect square.

Return the number of permutations of A that are squareful. Two permutations `A1` and `A2` differ if and only if there is some index `i` such that `A1[i] != A2[i]`.

Example 1:

``````Input: [1,17,8]
Output: 2
Explanation:
[1,8,17] and [17,8,1] are the valid permutations.
``````

Example 2:

``````Input: [2,2,2]
Output: 1
``````

Note:

1. 1 <= A.length <= 12
2. 0 <= A[i] <= 1e9

## # 解题方法

### # 回溯法

C++代码如下：

``````class Solution {
public:
int numSquarefulPerms(vector<int>& A) {
sort(A.begin(), A.end());
vector<int> cur;
vector<bool> visited(A.size());
int res = 0;
dfs(A, visited, res, cur);
return res;
}
int squareful(int x, int y) {
int s = sqrt(x + y);
return s * s == x + y;
}
void dfs(vector<int>& A, vector<bool>& visited, int& res, vector<int>& cur) {
if (cur.size() == A.size()) {
++res;
return;
}
for (int i = 0; i < A.size(); ++i) {
if (visited[i]) continue;
if (i > 0 && !visited[i - 1] && A[i] == A[i - 1]) continue;
if (!cur.empty() && !squareful(cur.back(), A[i])) continue;
cur.push_back(A[i]);
visited[i] = true;
dfs(A, visited, res, cur);
visited[i] = false;
cur.pop_back();
}
}
};
``````

## # 日期

2019 年 2 月 28 日 —— 二月最后一天