lc996 正方形数组的数目

给定非负整数数组A[n]，返回A的不同排列数目，使用数组每对相邻元素之和是一个完全平方数。
1<=n<=12; 0<=A[i]<=1e9

状压dp，记dp[st][i]表示已选择数的状态为st，并且最后选择数的下标为i的方案数，对于某个状态st，枚举最后选择的数i是哪个，以及上一个最后选择的数j是哪个，进行转换。
由于A可能存在相同的元素，需要去重，假设A[i]有z个，那由这z个元素构成的相同排序数有z!个，因此答案要除以z!。

class Solution {
public:
    int dp[4096][12];
    bool check(int x) {
        int z = sqrt(x);
        return z * z == x;
    }
    int numSquarefulPerms(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < (1<<n); i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = 0;
            }
        }
        for (int st = 1; st < (1<<n); st++) {
            int m = __builtin_popcount(st);
            for (int i = 0; i < n; i++) if (st & (1<<i)) {
                if (m == 1) {
                    dp[st][i] = 1;
                    continue;
                }
                for (int j = 0; j < n; j++) if (j != i && (st & (1<<j)) && check(nums[i]+nums[j])) {
                    dp[st][i] += dp[st^(1<<i)][j];
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += dp[(1<<n)-1][i];
        }
        map<int,int> cnt;
        for (auto i : nums) cnt[i] += 1;
        for (auto [k,v] : cnt) {
            for (int i = 1; i <= v; i++) {
                ans /= i;
            }
        }
        return ans;
    }
};