題目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;}};