题目996：正方形数组的数目
给定一个非负整数数组 A，如果该数组每对相邻元素之和是一个完全平方数，则称这一数组为正方形数组。
返回 A 的正方形排列的数目。两个排列 A1 和 A2 不同的充要条件是存在某个索引 i，使得 A1[i] != A2[i]。
示例1：
输入：[1,17,8]输出：2解释：[1,8,17] 和 [17,8,1] 都是有效的排列。
输入：[2,2,2]输出：1
1 <= A.length <= 120 <= A[i] <= 1e9
分析
依旧回溯算法，在全排列的基础上加一些剪枝策略，否则会超时。
首先排序，相同的数字在相邻位置
对于相邻位置相同的数字，遍历时候可以只用一次，相同的数字跳过，因为会重复
不满足"正方形数组"条件的数字跳过，不进行下一步操作
代码
class Solution {public:int numSquarefulPerms(vector<int>& A) {std::sort(A.begin(), A.end());used.resize(A.size(), false);vector<int> tem;for (int i = 0, size = A.size(); i < size; ++i) {tem.push_back(A[i]);used[i] = true;BackTrace(A, tem);used[i] = false;tem.pop_back();}return sets.size();}set<vector<int>> sets;vector<bool> used;void BackTrace(vector<int>& A, vector<int> &tem) {if (tem.size() == A.size()) {sets.emplace(tem);return;}for (int i = 0, size = A.size(); i < size; ++i) {// 过滤掉相同的数字if (i > 0 && A[i] == A[i-1] && !used[i-1]) { continue; }if (!tem.empty()) {if (used[i]) { continue; }// 不满足条件的直接跳过if (!IsPerfectSquare(A[i] + tem.back())) { continue; }tem.push_back(A[i]);used[i] = true;BackTrace(A, tem);used[i] = false;tem.pop_back();}}}bool IsPerfectSquare(int num) { // 判断一个数是否是完全平方数int sqrt_n = static_cast<int>(sqrt(num));return pow(sqrt_n, 2) == num;}};