LeetCode 698. 划分为k个相等的子集
目录
题目描述
题意分析
题目要的是一个判定：能不能把数组里的每一个数恰好用一次，分成 k 组，使每组的和都一样。注意是「划分」不是「选出」，没有数可以被剩下，也没有数可以被用两次。
约束里最关键的信号是数组长度只有 16 量级，而 k 也很小。这个规模摆明了不指望多项式算法，而是允许指数级搜索，前提是剪枝要够狠。另一个信号是数字全为正整数，这保证了「往一组里加数，和只会变大不会变小」，超过目标就可以立刻放弃这条分支。
从和出发能马上得到两个必要条件：总和必须能被 k 整除，否则每组的和不是整数，直接无解；每组的目标和就是总和除以 k。另外任何一个数都不能超过目标和，否则它自己一个人就撑爆了所属的那一组。
边界要留意：最大值恰好等于目标和（合法，它独占一组）、数组里有大量重复值（会制造大量等价的搜索分支）、
k等于 1（整个数组就是唯一一组）、以及k等于数组长度（每个数各成一组）。
解法：逐桶回溯 + 对称剪枝
核心思路
若能划分成功，每个子集的目标和只能是
sum / k。因此先检查总和能否整除k，并排除最大元素超过目标和的情况。数组长度最多 16，适合回溯，但必须减少等价分支。本文逐个填桶：当前桶的和为
current，选取尚未使用且不会超过target的数；填满后再开下一个桶。递归不变量是：已完成的桶都恰好等于target，used标记了已完成桶和当前桶中的元素。当只剩一个桶时，剩余元素的总和必然等于target，可以直接成功。三个剪枝决定了效率：
- 降序选择：先放大数，让“不可能装下”的矛盾尽早暴露。
- 同层去重：同一递归层中，相同数值产生的后续状态完全相同；一个失败后无需再试相同值。
- 空桶对称剪枝：空桶尝试最大的未使用数仍失败时，直接返回。因为未开始的桶彼此没有区别，而这个最大数必然属于某个桶；可以把那个桶重命名为当前桶，所以换另一个数作为开头只是重复排列桶编号。
解题步骤
- 计算总和；不能被
k整除时直接返回false。- 排序数组，从末尾开始按降序选数；最大值超过
target时无解。- 回溯参数记录剩余桶数、当前桶可选下标上界和当前桶和。
- 当前桶达到
target时，重置下标上界与桶和，开始填下一个桶。- 枚举未使用且能放入当前桶的数，标记后递归，失败则撤销。
- 用
previous跳过同层已经失败的相同值；若失败发生在空桶的第一次选择，立即剪掉所有等价空桶分支。- 剩一个桶时直接返回
true。对
[4,3,2,3,5,2,1]、k = 4，目标和为 5。降序搜索会依次形成{5}、{4,1}、{3,2}，最后剩余{3,2}自动成立。
代码实现
import java.util.Arrays;
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(k^n)$，因为每个数都可能被尝试分配到多个桶；排序、同层去重和空桶剪枝会显著缩小实际搜索树，但不改变指数级上界。
- 空间复杂度：$O(n)$，
used数组与递归栈都至多为数组长度。
关键点总结
- 先用总和整除和最大值检查排除必定无解的输入。
- 降序选择不是为了正确性，而是为了更早触发超额剪枝。
previous去掉同一层的等值分支，不能跨递归层共享。- 空桶剪枝来自桶编号的对称性：强制最大的未使用数进入当前空桶不会漏解。
buckets == 1能直接成功，依赖“前面每个桶都严格填满”的不变量。
易错点总结
- 不先判断
sum % k，整数除法会产生错误目标和。- 新开一个桶时必须把
start重置到数组末尾，否则会漏掉此前下标较大的未使用元素。- 递归失败后要同时撤销
used[i]并记录previous，否则状态污染或去重失效。- 空桶剪枝只能在
current == 0时使用；桶中已有元素时直接返回会误剪合法组合。- 不排序仍可能正确，但大数太晚参与会让大量分支直到深层才失败，容易超时。
- 排序会原地修改
nums；题目允许这样做，若调用方要求保留输入则需先复制。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 416. 分割等和子集 | 中等 | k=2 的特例，01 背包 |
| 473. 火柴拼正方形 | 中等 | k 固定为 4 的同型题 |
| 39. 组合总和 | 中等 | 凑定值的组合枚举 |
| 90. 子集 II | 中等 | 同层等值去重 |
| 47. 全排列 II | 中等 | 重复元素的排列剪枝 |
| 51. N 皇后 | 困难 | 回溯配合可行性剪枝 |