LeetCode 补充题 175. 等和划分的最大组数
题目描述
:::fold-green 相关原题
LeetCode 原题： ✅ 698. 划分为k个相等的子集
:::
给定正整数数组
nums，将所有元素恰好划分到若干个非空组，使每组元素和相同，返回最大组数。分组不要求连续。本文采用适用于
n≤16的状态压缩实现。
示例 1：
输入：
nums = [1,1,2,2,3,3]
输出：4
解释： 可分成[3]、[3]、[1,2]、[1,2]四组，每组和为 3；组数不可能更多。
提示：
- 本文实现适用于
n≤16的正整数数组。 - 所有元素恰好使用一次，组必须非空，组内元素不要求连续。
题意分析
所有元素为正且每组非空，组数最多为元素个数；组和相同还要求总和能被组数整除。按组数从大到小尝试，第一个能完成划分的候选就是答案。
解法：枚举组数并用掩码记录未满组和
核心思路
[!blue]
固定组数后设组和为
target。mask表示已经使用的下标集合，dp[mask]保存最后一组当前累计的和，-1 表示不可达；此前的组都已经凑满。初始空集合的累计和为 0。从可达状态追加一个未用元素，只有不超过
target才允许转移；恰好凑满时取模回到 0，表示下一次开始新组。元素为正使target为正，也保证完成的组不会为空。一个掩码的元素总和固定，所以可达时的余数始终等于该总和模
target，不同分组顺序不需要分别记录。满掩码可达且余数为 0，就说明全部元素被恰好用完并形成所需组数。
解题步骤
- 从 n 向 1 枚举组数，只保留能整除总和的候选。
- 设每组目标和，dp[mask] 保存当前未满组的和，-1 表示不可达。
- 追加一个未用元素且不超过目标和；凑满时余数回到 0。
- 完整掩码可达且余数为 0 时立即返回当前组数。
代码实现
class Solution {
public int maxGroups(int[] a) {
int n = a.length;
long sum = 0;
for (int v : a) {
sum += v;
}
for (int groups = n; groups >= 1; groups--) {
if (sum % groups != 0) {
continue;
}
long target = sum / groups;
long[] dp = new long[1 << n];
Arrays.fill(dp, -1);
dp[0] = 0;
for (int mask = 0; mask < dp.length; mask++) {
if (dp[mask] >= 0) {
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) == 0 && dp[mask] + a[i] <= target) {
dp[mask | (1 << i)] = (dp[mask] + a[i]) % target;
}
}
}
}
if (dp[dp.length - 1] == 0) {
return groups;
}
}
return 0;
}
}
func maxGroups(a []int) int {
n := len(a)
sum := int64(0)
for _, v := range a {
sum += int64(v)
}
for groups := n; groups >= 1; groups-- {
if sum%int64(groups) != 0 {
continue
}
target := sum / int64(groups)
dp := make([]int64, 1<<n)
for i := 1; i < len(dp); i++ {
dp[i] = -1
}
for mask := range dp {
if dp[mask] < 0 {
continue
}
for i, v := range a {
if mask&(1<<i) == 0 && dp[mask]+int64(v) <= target {
dp[mask|(1<<i)] = (dp[mask] + int64(v)) % target
}
}
}
if dp[len(dp)-1] == 0 {
return groups
}
}
return 0
}
复杂度分析
- 时间复杂度：最坏 $O(n^2\cdot 2^n)$。
- 空间复杂度：额外空间 $O(2^n)$。
关键点总结
[!green]
一个掩码对应已使用元素的固定总和，模目标值后的余数唯一，因此不必把组内排列再作为状态。
易错点总结
[!yellow]
只能用于所述小规模正整数输入；若允许0，总和0必须单独处理。连续分段是另一道问题。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 698. 划分为k个相等的子集 | 中等 | 固定组数的等和划分作为判定子问题，本题从大到小枚举可整除总和的组数。 |
| 473. 火柴拼正方形 | 中等 | 相当于固定分成四个等和组，本题组数可变，但每个元素仍需恰好使用一次。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！