给定一个非负整数数组 A，如果该数组每对相邻元素之和是一个完全平方数，则称这一数组为正方形数组。
返回 A 的正方形排列的数目。两个排列 A1 和 A2 不同的充要条件是存在某个索引 i，使得 A1[i] != A2[i]。
示例 1： 输入：[1,17,8] 输出：2 解释： [1,8,17] 和 [17,8,1] 都是有效的排列。 示例 2： 输入：[2,2,2] 输出：1 提示： 1 <= A.length <= 12 0 <= A[i] <= 1e9来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/number-of-squareful-arrays 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
类似题目： LeetCode 47. 全排列 II（回溯+搜索剪枝） LeetCode 46. 全排列（回溯）
class Solution { int ans = 0; public: int numSquarefulPerms(vector<int>& A) { vector<bool> vis(A.size(), false); sort(A.begin(), A.end()); dfs(A, 0, -1, vis); return ans; } void dfs(vector<int>& A, int count, int prev, vector<bool>& vis) { if(count == A.size()) { ans++; return; } for(int i = 0; i < A.size(); ++i) { if(i > 0 && !vis[i-1] && A[i-1]==A[i]) continue;// 剪枝 if(!vis[i] && (prev == -1 || ok(prev, A[i]))) { vis[i] = true; dfs(A, count+1, A[i], vis); vis[i] = false; } } } bool ok(int a, int b) { int num = sqrt(a+b); return num*num == a+b; } };4 ms 7.8 MB
我的博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！
