题目解析

一个数组，需要每两个相邻的数之和是完美平方，完美平方就是它们的和开方后是整数，需要找到所有满足条件的排列。
例子如下：

1
2
3
输入: [1,17,8]
输出: 2
解释: [1,8,17] 和 [17,8,1] 是正确的排列。比如[1,8,17]，1+8=9是完美平方，8+17也是完美平方

方法

这里的思路是暴力得到所有的排列，在递归过程中使用if (can(A, start))剪掉不能与前一个元素构成完美平方的元素，使用unordered_set<string>去除重复的排列。因为只会遍历成功的节点，最坏情况下时间复杂度O(n!)，因为剪枝，所以运行时间还行，4ms跑完。

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
32
33
34
35
36
37
class Solution {
public:
    int numSquarefulPerms(vector<int>& A) {
        helper(A, 0);
        return result;
    }
    void helper(vector<int> &A, int start) {
        if (start == A.size()) {
            ostringstream oss;
            copy(A.begin(), A.end()-1,ostream_iterator<int>(oss, ",")); // 将数组变成字符串
            string per = oss.str();
            if (has.find(per) != has.end()) return;
            has.insert(per);
            result++;
            return;
        }
        
        for (int i = start; i < A.size(); i++) {
            if (i != start && A[i] == A[start]) continue;
            if (i != start && i+1 < A.size() && A[i] == A[i+1]) continue;
            swap(A[i], A[start]);
            if (can(A, start)) {
                helper(A, start+1);   
            }
            swap(A[i], A[start]);
        }
    }
    bool can(vector<int> &A, int start){
        if (start > 0) {
            int y=(int)sqrt(A[start] + A[start-1]); // 判断是否能开方
            if (y*y != (A[start] + A[start-1])) return false;
        }
        return true;
    }
    unordered_set<string> has;
    int result = 0;
};