LeetCode 题解工作台
好子集的数目
给你一个整数数组 nums 。如果 nums 的一个子集中，所有元素的乘积可以表示为一个或多个 互不相同的质数 的乘积，那么我们称它为 好子集 。 比方说，如果 nums = [1, 2, 3, 4] ： [2, 3] ， [1, 2, 3] 和 [1, 3] 是 好 子集，乘积分别为 6 = 2*…
8
题型
4
代码语言
3
相关题
当前训练重点
困难 · 数组·哈希·扫描
答案摘要
注意到题目中 的范围为 $[1, 30]$，因此我们可以预处理出所有小于等于 的质数，即 $[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]$。 好子集中，所有元素的乘积可以表示为一个或多个互不相同的质数的乘积，也即是说，每个质因数最多只能出现一次。因此，我们可以使用一个二进制数来表示一个子集中的质因数，其中二进制数的第 位表示质数 是否出现在子集中。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个整数数组 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 ，可以表示为互不相同质数 2，3 和 5 的乘积。 - [3]：乘积为 3 ，可以表示为质数 3 的乘积。 - [15]：乘积为 15 ，可以表示为互不相同质数 3 和 5 的乘积。
提示：
1 <= nums.length <= 1051 <= nums[i] <= 30
解题思路
方法一：状态压缩动态规划
注意到题目中 的范围为 ，因此我们可以预处理出所有小于等于 的质数，即 。
好子集中，所有元素的乘积可以表示为一个或多个互不相同的质数的乘积，也即是说，每个质因数最多只能出现一次。因此，我们可以使用一个二进制数来表示一个子集中的质因数，其中二进制数的第 位表示质数 是否出现在子集中。
我们可以使用状态压缩动态规划的方法来求解本题。设 表示二进制数 表示的子集中的质因数的乘积为一个或多个互不相同的质数的乘积的方案数。初始时 。
我们在 的范围内枚举一个数 ，如果 不在 中，或者 为 的倍数，那么我们可以直接跳过。否则，我们可以将 的质因数用一个二进制数 表示，然后我们从大到小枚举当前的状态 ，如果 与 按位与的结果为 ，那么我们可以从状态 转移到状态 ，转移方程为 ，其中 表示 在 中出现的次数。
注意，我们没有从数字 开始枚举，因为我们可以选择任意个数字 ，加入到好子集中。那么最终的答案为 。
时间复杂度 ，空间复杂度 。其中 为 的长度；而 和 分别为题目中 的范围和状态的个数，本题中 , 。
相似题目：
class Solution:
def numberOfGoodSubsets(self, nums: List[int]) -> int:
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
cnt = Counter(nums)
mod = 10**9 + 7
n = len(primes)
f = [0] * (1 << n)
f[0] = pow(2, cnt[1])
for x in range(2, 31):
if cnt[x] == 0 or x % 4 == 0 or x % 9 == 0 or x % 25 == 0:
continue
mask = 0
for i, p in enumerate(primes):
if x % p == 0:
mask |= 1 << i
for state in range((1 << n) - 1, 0, -1):
if state & mask == mask:
f[state] = (f[state] + cnt[x] * f[state ^ mask]) % mod
return sum(f[i] for i in range(1, 1 << n)) % mod
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the approach. The prime factorization of numbers in `nums` takes constant time due to the limited range (1 to 30). Space complexity is driven by the number of distinct prime factorizations, which is manageable due to the small number range. Modulo operations ensure manageable size of results. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Can the candidate efficiently handle prime factorization for larger input sizes?
- question_mark
Is the candidate familiar with bit manipulation and dynamic programming?
- question_mark
Does the candidate handle modular arithmetic correctly in their solution?
常见陷阱
外企场景- error
Overlooking the need for distinct prime factorizations can result in incorrect subset counting.
- error
Not using modulo $10^9 + 7$ can cause overflow issues when dealing with large inputs.
- error
Not optimizing prime factorization by considering only relevant numbers can lead to inefficient solutions.
进阶变体
外企场景- arrow_right_alt
Consider a variant where all numbers in `nums` are prime, and explore how the solution changes.
- arrow_right_alt
A version where you must find subsets that can be formed with exactly `k` distinct primes.
- arrow_right_alt
Handling constraints where `nums` contains larger numbers beyond 30 could add complexity.