平方数组的数目Java
文章发布较早，内容可能过时，阅读注意甄别。
# 题目
如果一个数组的任意两个相邻元素之和都是 完全平方数 ，则该数组称为 平方数组 。
给定一个整数数组 nums，返回所有属于 平方数组 的 nums 的排列数量。
如果存在某个索引 i 使得 perm1[i] != perm2[i]，则认为两个排列 perm1 和 perm2 不同。
示例 1：
输入：nums = [1,17,8] 输出：2 解释：[1,8,17] 和 [17,8,1] 是有效的排列。 示例 2：
输入：nums = [2,2,2] 输出：1
提示：
- 1 <= nums.length <= 12
- 0 <= nums[i] <= 109
# 思路
状压+去重
# 解法
class Solution {
private int n;
private int[] nums;
private int[][] memo;
public int numSquarefulPerms(int[] nums) {
this.nums = nums;
n = nums.length;
memo=new int[1<<n][n];
for(var a:memo) Arrays.fill(a,-1);
Arrays.sort(nums);
return dfs(0, 0);
}
public int dfs(int s, int pre) {
if (s == (1 << n) - 1) {
return 1;
}
int j = Integer.bitCount(s);
int ans = 0;
//同一层不能添加相同数据
if(memo[s][pre]!=-1) return memo[s][pre];
for (int i = 0; i < n; i++) {
//如果相邻 并且不是第一个 且上一个没选 代表这种方案不行 重复啦
if(i>0&&(s>>(i-1)&1)==0&&nums[i]==nums[i-1]) continue;
if (((s >> i & 1) == 0 && isValid(nums[i] +nums[pre])) || j == 0) {
ans += dfs(s | 1 << i, i);
}
}
return memo[s][pre]=ans;
}
public boolean isValid(int i) {
int a = (int) Math.sqrt(i);
return i == a * a;
}
}
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
38
39
40
41
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
38
39
40
41
# 总结
- 分析出几种情况，然后分别对各个情况实现
