题目地址：https://leetcode.com/problems/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；
题目大意
给出了一个非负数字组成的数组，如果一个数组是可平方的，那么这个数组每两个相邻的元素的和是一个平方数字。判断给出的数组的所有排列中，有多少个不同的排列是可平方的。
解题方法
回溯法
这个题的问题规模只有12个，也就是提醒我们可以使用O(N!)的算法，所以可以直接使用回溯法。
首先要排序使得相同的数字都排列在一起，这个题的回溯策略是使用visited数组表示每个数字是否用过了，从起点位置0开始，每次向后遍历，如果后面的这个数字没有用过，并且如果前面的数字和它相同、那么前面的数字也没有用过，和前面的数字相加是可以平方的，那么把当前数字放到路径cur中，设置当前的数组访问状态为已访问，然后继续从0开始遍历即可。
这个题虽然是Hard，但是还不是很难，应该会才对。
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();
}
}
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
参考资料：https://zxi.mytechroad.com/blog/searching/leetcode-996-number-of-squareful-arrays/
2022
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发