LC 1994. 好子集的数目
题目描述
这是 LeetCode 上的 1994. 好子集的数目 ，难度为 困难。
给你一个整数数组 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中不同的 好 子集的数目对 $10^9 + 7$ 取余 的结果。
nums 中的 子集 是通过删除 nums 中一些（可能一个都不删除，也可能全部都删除）元素后剩余元素组成的数组。如果两个子集删除的下标不同，那么它们被视为不同的子集。
示例 1：1
2
3
4
5
6
7
8
9
10
11输入：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：1
2
3
4
5
6
7
8
9
10输入：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 <= 10^5$
- $1 <= nums[i] <= 30$
状压 DP
该问题属于 NP 完全问题，注定不存在多项式解决方案，只能通过「爆搜 + 剪枝」或「状压 DP」来求解。
对子集的乘积进行质数分解，等价于对子集每一位数进行质数分解。
一个显然的突破口是 $1 <= nums[i] <= 30$，再加上题目对于「好子集」的定义，我们可以进一步缩减可选数的数量，不超过 $30$ 的质数个数包括 $[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]$（共 $10$ 个），将其记作 $p$，在一个好子集中，每个 $p[i]$ 最多出现一次。
同时，题目规定数值相同，下标不同均视为不同方案，因此我们可以先使用数组 $cnts$ 统计在 $nums$ 中每个数的出现次数，$cnts[val] = x$ 含义为数值 $val$ 在 $nums$ 中的出现次数为 $x$ 次。
使用的数有限（共 $10$ 个），并且使用到的数最多出现一次，容易想到使用「状压 DP」来求解：我们使用一个二进制数来表示好子集乘积最终能拆解成哪些质数，如果拆解结果中包含 $p[i]$，对应的二进制表示中的第 $i$ 位则为 $1$，否则为 $0$。
定义 $f[state]$ 为当前子集乘积拆解结果的用到的质数为 $state$ 时的方案数，$state$ 为一个长度 $10$ 的二进制数，若 $state$ 中的第 $k$ 位二进制表示为 $1$，代表数值 $p[k]$ 在拆解结果中出现过；若第 $k$ 位二进制表示为 $0$ 代表 $p[k]$ 在拆解结果中没出现过。
我们有起始化条件：空集，即 $f[0] = 1$。
不失一般性考虑 $f[s]$ 该如何计算：从前往后考虑每个数值（范围 $[2, 30]$ 的数，$1$ 添加与否不对好子集产生影响，最后讨论）是否可以加入到子集中，一个数值 $t$ 能够添加到子集中的充要条件为题目给定的条件：该数不会被相同的质数相乘表示。
如果一个数值 $t$ 能够添加到好子集中，我们通过「试除法」将其分解为 $p$ 中的多个质数，并使用二进制数 $cur$ 来表示用到了 $p$ 中的哪些质数，然后需要判断 $t$ 能够添加到那些子集中，其实就是枚举与 $cur$ 无交集的状态 $prev$，最终的 $f[s]$ 为「所有合法的 $prev$ 的状态数 $f[prev]$」与「数值 $t$ 的出现次数 $cnts[t]$ 」的乘积之和。
需要注意的是，由于我们是从范围 $[2, 30]$ 范围内从前往后考虑每个 $t$，因此在枚举 $prev$ 时需要进行倒序遍历，确保计算 $f[s]$ 所依赖的 $f[prev]$ 为不考虑当前数值 $t$ 时的方案数。
由「质数 $p$ 组成的好子集方案数」为 $ans = \sum_{state’ = 1}^1024 f[state’]$，其中 $state’$ 对应一个合法的好子集方案。
在此基础上，再考虑数值 $1$ 对答案的影响：在每个合法的 $state’$ 前提下，增加若干个 $1$ 并不影响子集乘积（即好子集增加 $1$ 后仍为好子集），因此每个合法子集 $state’$ 可以对应出 $2^{cnts[1]}$ 个具体方案（代表每个 $1$ 即可以选，也可以不选）。
代码：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
41class Solution {
int MOD = (int)1e9+7;
int[] p = new int[]{2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
int[] cnts = new int[35];
public int numberOfGoodSubsets(int[] nums) {
int n = nums.length;
for (int i : nums) cnts[i]++;
int mask = 1 << 10;
long[] f = new long[mask];
f[0] = 1;
for (int i = 2; i <= 30; i++) {
if (cnts[i] == 0) continue;
// 对 i 进行试除
int cur = 0, x = i;
boolean ok = true;
for (int j = 0; j < 10 && ok; j++) {
int t = p[j], c = 0;
while (x % t == 0) {
cur |= (1 << j);
x /= t; c++;
}
// 如果 i 能够被同一质数试除多次，说明 i 不能加到子集，跳过
if (c > 1) ok = false;
}
if (!ok) continue;
// 枚举前一状态 prev
//（确保考虑一个新数值 i 时，依赖的子集 prev 存储的为尚未考虑 i 的方案数）
for (int prev = mask - 1; prev >= 0; prev--) {
// 只有当前选择数与前一状态不冲突，则能够进行转移，将方案数进行累加
if ((prev & cur) != 0) continue;
f[prev | cur] = (f[prev | cur] + f[prev] * cnts[i]) % MOD;
}
}
long ans = 0;
// 统计所有非空集的方案数
for (int i = 1; i < mask; i++) ans = (ans + f[i]) % MOD;
// 在此基础上，考虑每个 1 选择与否对答案的影响
for (int i = 0; i < cnts[1]; i++) ans = ans * 2 % MOD;
return (int) ans;
}
}
- 时间复杂度：预处理每个数值的出现次数复杂度为 $O(n)$；令数值范围 $C = 30$，状态数为 $M = 1024$，DP 部分复杂度为 $O(C \times M)$。整体复杂度为 $O(n + C \times M)$
- 空间复杂度：$O(C + M)$
关于「倒序遍历」状态的答疑
上述的分析推理基于我们进行了「一维空间优化」。
原始的状态定义应该是 $f[i][state]$ 为考虑范围在 $[1,30]$ 的前 $i$ 个数，并且好子集拆解结果的用到的质数为 $state$ 时的方案数。
我们有显然的初始化条件：$f[1][0] = 1$，代表当只有数值 $1$ 的话，只有空集为合法方案。
不失一般性的考虑 $f[i][s]$ 该如何计算，根据使用数值 $i$ 来进行分情况讨论：
- 不考虑数值 $i$（或是数值 $i$ 在 $nums$ 中没有出现，无法考虑），则有 $f[i][s] = f[i - 1][s]$；
- 考虑数值 $i$，分析方法同「一维空间优化」，对数值 $i$ 应用「试除法」拆解成对应的质数状态 $cur$，然后找到可以转移的前一状态 $prev$ 来尝试转移，则有 $f[i][cur | prev] = f[i][cur | prev] + f[i - 1][prev]$。
基于对「原始状态定义」的分析，我们发现 $f[i][cur | prev]$ 的更新（累加）依赖于 $f[i][prev]$，同时 $prev$ 是 $cur | prev$ 的子集，因此在进行「一维空间优化」，我们需要确保所依赖的状态没有被覆盖更新，即采用「倒序遍历」。
代码：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
34class Solution {
int MOD = (int)1e9+7;
int[] p = new int[]{2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
int[] cnts = new int[35];
public int numberOfGoodSubsets(int[] nums) {
for (int i : nums) cnts[i]++;
int mask = 1 << 10;
long[][] f = new long[35][mask];
f[1][0] = 1;
for (int i = 2; i <= 30; i++) {
for (int s = 0; s < mask; s++) f[i][s] = f[i - 1][s];
if (cnts[i] == 0) continue;
int cur = 0, x = i;
boolean ok = true;
for (int j = 0; j < 10 && ok; j++) {
int t = p[j], c = 0;
while (x % t == 0) {
cur |= (1 << j);
x /= t; c++;
}
if (c > 1) ok = false;
}
if (!ok) continue;
for (int prev = 0; prev < mask; prev++) {
if ((prev & cur) != 0) continue;
f[i][prev | cur] = (f[i][prev | cur] + f[i - 1][prev] * cnts[i]) % MOD;
}
}
long ans = 0;
for (int i = 1; i < mask; i++) ans = (ans + f[30][i]) % MOD;
for (int i = 0; i < cnts[1]; i++) ans = ans * 2 % MOD;
return (int) ans;
}
}
- 时间复杂度：预处理每个数值的出现次数复杂度为 $O(n)$；令数值范围 $C = 30$，状态数为 $M = 1024$，DP 部分复杂度为 $O(C \times M)$。整体复杂度为 $O(n + C \times M)$
- 空间复杂度：$O(C \times M)$
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1994 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！
