题目描述

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

题意：给定一个非负整数数组 A，如果该数组每对相邻元素之和是一个完全平方数，则称这一数组为正方形数组。返回 A 的正方形排列的数目。

算法1

(回溯) $O(n*n!)$

题解：对于包括重复元素的排列与组合问题，我都喜欢先用一个哈希表存储每个元素出现的个数，然后在枚举的时候只对哈希表进行枚举这样就避免了重复元素。
具体到这一题，我们可以预先处理好数组中两个数的和中哪些数是平方数。
进行dfs时，我们要记录的状态是上一个选择的数是多少以及当前已经选了多少个数了，另一个全局的状态是哈希表，表示当前每个数字还剩多少个可以选。
如果已经将数组中的数都选择完了，答案加上1。否则遍历所有还可以选择的数并且这个数和上一个选择的数和是平方数，递归进行搜索。
此外，提供了一种不使用乘法和除法来判断一个数是不是完全平方数。
因为
1 + 3 + 5 + 7 +...+ (2n - 1) = n^2

class Solution {
public:
    map<int,int> hash;
    set<int> s_hash;
    int res = 0;
    int numSquarefulPerms(vector<int>& A) {
        for(auto x:A) hash[x] ++;
        int n = A.size();
        for(int i = 0 ; i < n ; i ++)
            for(int j = i + 1;j < n ; j ++)
                if(issquare(A[i] + A[j]))
                    s_hash.insert(A[i] + A[j]);
        dfs(0,0,n);
        return res;
    }
    bool issquare(int x) {
        int t = sqrt(x);
        return t * t == x;
    }
    bool issquare2(int n)
    {
        for(int i = 1; n > 0; i += 2) n -= i;
        return n == 0;
    }
    void dfs(int pre,int cnt,int n)
    {
        if(cnt == n) {res ++;return;}
        for(auto & it:hash)
        {
            if(it.second > 0 && (cnt == 0 || s_hash.count(it.first + pre) == 1))
            {
                it.second --;
                dfs(it.first,cnt + 1,n);
                it.second ++;
            }
        }
    }
};