平方数组的数目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] <= 10⁹

# 思路

状压+去重

# 解法

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

# 总结

分析出几种情况，然后分别对各个情况实现

#Java