题目描述
给定一个非负整数数组 A
,如果该数组每对相邻元素之和是一个完全平方数,则称这一数组为 正方形 数组。
返回 A
的正方形排列的数目。两个排列 A1
和 A2
不同的充要条件是存在某个索引 i
,使得 A1[i] != A2[i]
。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/number-of-squareful-arrays
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
样例
输入:[1,17,8]
输出:2
解释:
[1,8,17] 和 [17,8,1] 都是有效的排列。
输入:[2,2,2]
输出:1
限制
1 <= A.length <= 12
0 <= A[i] <= 1e9
算法
(状态压缩动态规划) $O(2^n \cdot n^2)$
- 首先我们不考虑重复的情况,即假设排列的下标不同就是不同的排列,我们尝试用动态规划求解。
- 状态 $f(S, i)$ 表示已经用了集合 $S$ 中的数字,且最后一个数字的下标为 $i$,合法可平方排列的方案数,这里的集合 $S$ 用一个二进制数来表示,二进制位 $b_k$ 为 0 代表第 $k$ 个数字没用过。
- 初始时 $f(1 << i, i) = 1$,其余为 0。转移时,首先枚举 $j$ 使得 $j$ 不在 $S$ 中,然后判断 $A[i] + A[j]$ 是否为完全平方数,如果符合条件,则 $f(S | 1 << j, j) = f(S | 1 << j) + f(S, i)$。
- 最终答案为,$\sum_{i=0}^{n} f((1 << n) - 1, i)$。
- 然后需要处理重复的情况,由排列转组合的经验得知,我们只需要找到数组
A
中每种数字出现的次数,用答案除以每种数字出现次数的阶乘即可。
时间复杂度
- 状态数为 $O(2^n \cdot n)$,转移需要 $O(n)$ 的时间,去重需要首先排序,然后扫一遍,故总时间复杂度为 $O(2^n \cdot n^2)$。
空间复杂度
- 需要状态数这么多的空间,故空间复杂度为 $O(2^n \cdot n)$。
C++ 代码
class Solution {
public:
bool isSquare(int x) {
int t = sqrt(x);
return t * t == x;
}
int fact(int x) {
int t = 1;
for (int i = 2; i <= x; i++)
t *= i;
return t;
}
int numSquarefulPerms(vector<int>& A) {
int n = A.size();
sort(A.begin(), A.end());
vector<int> s;
int cnt = 1;
for (int i = 1; i < n; i++) {
if (A[i] != A[i - 1]) {
s.push_back(cnt);
cnt = 0;
}
cnt++;
}
s.push_back(cnt);
vector<vector<int>> f(1 << n, vector<int>(n, 0));
for (int i = 0; i < n; i++)
f[1 << i][i] = 1;
for (int S = 1; S < 1 << n; S++)
for (int i = 0; i < n; i++)
if (S & (1 << i))
for (int j = 0; j < n; j++)
if (!(S & (1 << j)) && isSquare(A[i] + A[j])) {
f[S | (1 << j)][j] += f[S][i];
}
int ans = 0;
for (int i = 0; i < n; i++)
ans += f[(1 << n) - 1][i];
for (int i = 0; i < s.size(); i++)
ans /= fact(s[i]);
return ans;
}
};