LeetCode 698. 划分为k个相等的子集
题目描述
题意分析
把数组中的每个数恰好使用一次，分成
k个非空子集；子集不要求在原数组中连续，只要求元素和相等。所有数都是正数，所以每组目标和只能是target = sum / k。总和不能被
k整除，或最大元素已经超过target，都一定无解。但通过这两项检查不代表一定能分组，仍要搜索各个数的归属。数组长度不超过16，可以用回溯枚举组合，再通过重复状态与对称性剪枝。
解法：逐桶回溯 + 对称剪枝
核心思路
[!blue]
把每个子集看成一个容量为
target的桶，先装满当前桶，再开始下一个。buckets是包括当前桶在内尚未完成的桶数，current是当前桶的和，start是当前桶下一次允许选择的最大下标；used[i]表示该元素已经进入已完成的桶或当前桶。先升序排序，再从末尾往前选数，大数更容易让桶超额，能较早暴露不可行分支。加入
nums[i]后，递归只继续考虑i - 1及以前的下标。同一组元素总能按下标递减的顺序选出，因此这样不会漏掉组合，只会去掉同一组合的不同选择顺序。新开桶时必须重新从数组末尾开始，才能使用上一桶跳过的大数。搜索中始终保证已完成的桶恰好等于
target，当前桶不超过target，且每个元素最多使用一次。由于元素全为正数，current + nums[i] > target后无法靠加入其他元素降低和，可以直接跳过。递归失败时撤销used[i]，恢复到选择它之前的状态，再试下一个候选。
previous只记录当前循环中已经尝试失败的值。如果随后遇到相同值，交换这两个等值元素的身份不会改变任何桶的和；而先前下标较大的元素被选中时，后面的等值元素仍可继续使用，所以需要多个相同值的组合也已经覆盖。这里跳过的是同一层的等价选择，不能在不同递归层之间共享previous。当前桶为空时，第一个候选一定是最大的未使用元素。任何合法划分中，这个数总属于某个剩余桶；这些桶没有编号上的区别，可以把包含它的桶改名为当前桶。因此只需枚举“当前桶包含这个数”的所有组合；这一整条分支失败后，就可以直接判定当前状态无解。桶里已有元素时，这些元素已经固定了当前桶的组成，不能再通过交换桶名强制加入某个候选，所以该剪枝只能用于
current == 0。当前桶装满后，将
buckets减一并重置current、start。只剩一个桶时，已完成桶用掉了(k - 1) * target，所有未使用元素的和必然等于target，直接把它们放入最后一桶即可。因为target > 0，每个填满的桶及最后一桶都必定非空。
解题步骤
- 计算总和；不能被
k整除时直接返回false。- 排序数组，从末尾开始按降序选数；最大值超过
target时无解。- 回溯参数记录剩余桶数、当前桶可选下标上界和当前桶和。
- 当前桶达到
target时，重置下标上界与桶和，开始填下一个桶。- 枚举未使用且能放入当前桶的数，标记后递归，失败则撤销。
- 用
previous跳过同层已经失败的相同值；若失败发生在空桶的第一次选择，立即剪掉所有等价空桶分支。- 剩一个桶时直接返回
true。
k == 1时，全部元素本来就构成唯一一组，搜索入口会直接成功。previous使用-1作为初值，依赖题目保证元素全为正数；正数条件同时支撑超额剪枝和非空性判断。
代码实现
class Solution {
public boolean canPartitionKSubsets(int[] nums, int k) {
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % k != 0) {
return false;
}
int target = sum / k;
Arrays.sort(nums);
if (nums[nums.length - 1] > target) {
return false;
}
return fill(nums, new boolean[nums.length], k, nums.length - 1, 0, target);
}
private boolean fill(
int[] nums, boolean[] used, int buckets, int start, int current, int target) {
// 前面的桶均已装满，总和守恒保证最后一桶无需继续搜索。
if (buckets == 1) {
return true;
}
if (current == target) {
return fill(nums, used, buckets - 1, nums.length - 1, 0, target);
}
int previous = -1;
for (int i = start; i >= 0; i--) {
if (used[i] || nums[i] == previous || current + nums[i] > target) {
continue;
}
used[i] = true;
if (fill(nums, used, buckets, i - 1, current + nums[i], target)) {
return true;
}
// 只在当前尝试失败后撤销占用，让后续兄弟选择复用元素。
used[i] = false;
previous = nums[i];
// 空桶可交换编号，最大的未用数放本桶失败后无需换其他开头。
if (current == 0) {
return false;
}
}
return false;
}
}
import "sort"
func canPartitionKSubsets(nums []int, k int) bool {
sum := 0
for _, num := range nums {
sum += num
}
if sum%k != 0 {
return false
}
target := sum / k
sort.Ints(nums)
if nums[len(nums)-1] > target {
return false
}
return fillBuckets(nums, make([]bool, len(nums)), k, len(nums)-1, 0, target)
}
func fillBuckets(nums []int, used []bool, buckets, start, current, target int) bool {
// 前面的桶均已装满，总和守恒保证最后一桶无需继续搜索。
if buckets == 1 {
return true
}
if current == target {
return fillBuckets(nums, used, buckets-1, len(nums)-1, 0, target)
}
previous := -1
for i := start; i >= 0; i-- {
if used[i] || nums[i] == previous || current+nums[i] > target {
continue
}
used[i] = true
if fillBuckets(nums, used, buckets, i-1, current+nums[i], target) {
return true
}
// 只在当前尝试失败后撤销占用，让后续兄弟选择复用元素。
used[i] = false
previous = nums[i]
// 空桶可交换编号，最大的未用数放本桶失败后无需换其他开头。
if current == 0 {
return false
}
}
return false
}
复杂度分析
- 时间复杂度：最坏为指数级。按元素在各桶中的分配估算，回溯可取保守上界 $O(nk^n)$，其中 $n$ 包含每个状态扫描候选元素的成本；此外排序需要 $O(n \log n)$。剪枝能减少实际搜索量，但不能把最坏情况变成多项式时间。
- 空间复杂度：$O(n)$，
used保存每个元素的占用情况，递归深度包括至多 $n$ 次选数和 $k-1$ 次换桶，而 $k \le n$。
关键点总结
[!green]
- 先用总和整除和最大值检查排除必定无解的输入。
- 降序选择不是为了正确性，而是为了更早触发超额剪枝。
previous去掉同一层的等值分支，不能跨递归层共享。- 空桶剪枝来自桶编号的对称性：强制最大的未使用数进入当前空桶不会漏解。
buckets == 1能直接成功，依赖“前面每个桶都严格填满”的不变量。
易错点总结
[!yellow]
- 不先判断
sum % k，整数除法会产生错误目标和。- 新开一个桶时必须把
start重置到数组末尾，否则会漏掉此前下标较大的未使用元素。- 递归失败后要同时撤销
used[i]并记录previous，否则状态污染或去重失效。- 空桶剪枝只能在
current == 0时使用；桶中已有元素时直接返回会误剪合法组合。- 不排序仍可能正确，但大数太晚参与会让大量分支直到深层才失败，容易超时。
- 排序会原地修改
nums，搜索使用修改后的顺序。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 473. 火柴拼正方形 | 中等 | 火柴拼正方形是k=4的等和分组特例，同样需要把每个元素只分配到一组。 |
| 补充题 175. 等和划分的最大组数 | 中等 | 同属等和划分。固定组数后的可行性判定可复用；补充题再按总和的因子枚举组数，求最大可行值。 |
| 416. 分割等和子集 | 中等 | 同属等和划分。两组时只需找和为总和一半的子集；推广到 k 组后还要追踪其余分组的使用情况。 |