# 996. Number of Squareful Arrays

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`

``````class Solution {
public:
int numSquarefulPerms(vector<int>& A) {
int res = 0;
vector<int> visited(A.size()), out;
sort(A.begin(), A.end());
helper(A, 0, visited, out, res);
return res;
}
void helper(vector<int>& A, int level, vector<int>& visited, vector<int>& out, int& res) {
if (level >= A.size()) {
++res;
return;
}
for (int i = 0; i < A.size(); ++i) {
if (visited[i] == 1) continue;
if (i > 0 && A[i] == A[i - 1] && visited[i - 1] == 0) continue;
if (!out.empty()) {
double root = sqrt(A[i] + out.back());
if (root - floor(root) != 0) continue;
}
visited[i] = 1;
out.push_back(A[i]);
helper(A, level + 1, visited, out, res);
visited[i] = 0;
out.pop_back();
}
}
};
``````

``````class Solution {
public:
int numSquarefulPerms(vector<int>& A) {
int res = 0;
sort(A.begin(), A.end());
helper(A, 0, res);
return res;
}
void helper(vector<int> A, int start, int& res) {
if (start >= A.size()) ++res;
for (int i = start; i < A.size(); ++i) {
if (i > start && A[i] == A[start]) continue;
swap(A[i], A[start]);
if (start == 0 || (start > 0 && isSquare(A[start] + A[start - 1]))) {
helper(A, start + 1, res);
}
}
}
bool isSquare(int num) {
int r = sqrt(num);
return r * r == num;
}
};
``````

``````class Solution {
public:
int numSquarefulPerms(vector<int>& A) {
unordered_map<int, int> numCnt;
unordered_map<int, unordered_set<int>> numMap;
int res = 0, n = A.size();
for (int num : A) ++numCnt[num];
for (auto &a : numCnt) {
for (auto &b : numCnt) {
int x = a.first, y = b.first, r = sqrt(x + y);
if (r * r == x + y) numMap[x].insert(y);
}
}
for (auto &a : numCnt) {
helper(a.first, n - 1, numCnt, numMap, res);
}
return res;
}
void helper(int x, int left, unordered_map<int, int>& numCnt, unordered_map<int, unordered_set<int>>& numMap, int& res) {
if (left == 0) {
++res;
return;
}
--numCnt[x];
for (int y : numMap[x]) {
if (numCnt[y] > 0 ) {
helper(y, left - 1, numCnt, numMap, res);
}
}
++numCnt[x];
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/996

Permutations

Permutations II

https://leetcode.com/problems/number-of-squareful-arrays/

https://leetcode.com/problems/number-of-squareful-arrays/discuss/238593/Java-DFS-%2B-Unique-Perms

https://leetcode.com/problems/number-of-squareful-arrays/discuss/238562/C%2B%2BPython-Backtracking

https://leetcode.com/problems/number-of-squareful-arrays/discuss/238612/4msC%2B%2B-Simple-Backtracking-like-Permutations-II

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation