我们先来看题目描述给你一个整数数组 nums 。如果 nums 的一个子集中所有元素的乘积可以表示为一个或多个 互不相同的质数 的乘积那么我们称它为 好子集。比方说如果 nums [1, 2, 3, 4] [2, 3] [1, 2, 3] 和 [1, 3] 是 好 子集乘积分别为 6 2 * 3 6 2 * 3 和 3 3 。[1, 4] 和 [4] 不是 好 子集因为乘积分别为 4 2 * 2 和 4 2 * 2 。请你返回 nums 中不同的 好 子集的数目对 109 7 取余 的结果。nums 中的 子集 是通过删除 nums 中一些可能一个都不删除也可能全部都删除元素后剩余元素组成的数组。如果两个子集删除的下标不同那么它们被视为不同的子集。示例 1输入nums [1,2,3,4] 输出6 解释好子集为 - [1,2]乘积为 2 可以表示为质数 2 的乘积。 - [1,2,3]乘积为 6 可以表示为互不相同的质数 2 和 3 的乘积。 - [1,3]乘积为 3 可以表示为质数 3 的乘积。 - [2]乘积为 2 可以表示为质数 2 的乘积。 - [2,3]乘积为 6 可以表示为互不相同的质数 2 和 3 的乘积。 - [3]乘积为 3 可以表示为质数 3 的乘积。示例 2输入nums [4,2,3,15] 输出5 解释好子集为 - [2]乘积为 2 可以表示为质数 2 的乘积。 - [2,3]乘积为 6 可以表示为互不相同质数 2 和 3 的乘积。 - [2,15]乘积为 30 可以表示为互不相同质数 23 和 5 的乘积。 - [3]乘积为 3 可以表示为质数 3 的乘积。 - [15]乘积为 15 可以表示为互不相同质数 3 和 5 的乘积。提示1 nums.length 1051 nums[i] 30解决方案方法一状态压缩动态规划思路注意到题目规定数组 nums 中的元素不超过 30 因此我们可以将 [1,30] 中的整数分成如下三类1对于任意一个好子集而言我们添加任意数目的 1 得到的新子集仍然是好子集2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30 这些数均不包含平方因子因此每个数在好子集中至多出现一次4, 8, 9, 12, 16, 18, 20, 24, 25, 27, 28这些数包含平方因子因此一定不能在好子集中出现。我们可以通过硬编码的方式把 [1, 30] 中的整数按照上述分类也可以先预处理出所有 [1, 30] 中质数 2, 3, 5, 7, 11, 13, 17, 19, 23, 29再通过试除的方式动态分类。分类完成后我们就可以考虑动态规划了。由于每个质因数只能出现一次并且 [1, 30] 中一共有 10 个质数因此我们可以用一个长度为 10 的二进制数 mask 表示这些质因数的使用情况其中 mask 的第 i 位为 1 当且仅当第 i 个质数已经被使用过。代码Javaclass Solution { static final int[] PRIMES {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}; static final int NUM_MAX 30; static final int MOD 1000000007; public int numberOfGoodSubsets(int[] nums) { int[] freq new int[NUM_MAX 1]; for (int num : nums) { freq[num]; } int[] f new int[1 PRIMES.length]; f[0] 1; for (int i 0; i freq[1]; i) { f[0] f[0] * 2 % MOD; } for (int i 2; i NUM_MAX; i) { if (freq[i] 0) { continue; } // 检查 i 的每个质因数是否均不超过 1 个 int subset 0, x i; boolean check true; for (int j 0; j PRIMES.length; j) { int prime PRIMES[j]; if (x % (prime * prime) 0) { check false; break; } if (x % prime 0) { subset | (1 j); } } if (!check) { continue; } // 动态规划 for (int mask (1 PRIMES.length) - 1; mask 0; --mask) { if ((mask subset) subset) { f[mask] (int) ((f[mask] ((long) f[mask ^ subset]) * freq[i]) % MOD); } } } int ans 0; for (int mask 1, maskMax (1 PRIMES.length); mask maskMax; mask) { ans (ans f[mask]) % MOD; } return ans; } }复杂度分析时间复杂度O(n C × O(2π(C)) 。其中 n 是数组 nums 的长度C 是 nums 元素的最大值在本题中 C 30 π(x) 表示 ≤x 的质数的个数。我们一共需要考虑 O(C) 个数每个数需要 O(2π(C)) 的时间计算动态规划除此之外在初始时我们还需要遍历一遍所有的数时间复杂度为 O(n) 。空间复杂度O(2π(C)) 即为动态规划需要使用的空间。