划分为 K 个等和子集如何用回溯与剪枝求解？

简化版

先求数组总和，若不能被 k 整除直接失败，目标桶和是 sum / k。回溯把数字放入 k 个桶中，每个桶不能超过目标和；通常先降序排序大数优先放，再用“相同桶和跳过”“空桶失败即停止”等剪枝减少重复搜索。

详细版

这题可以理解为把每个数分配到某个桶，使所有桶的和都等于 target = sum / k。因为元素个数有限且每个元素只能用一次，回溯状态常写成 dfs(index, buckets)：处理第 index 个数，尝试放入每个桶。

核心剪枝包括：总和不能整除 k 直接返回；最大数大于 target 直接返回；数组降序排序，让失败尽早发生；若两个桶当前和相同，把数字放入它们会形成对称状态，只尝试一个；数字放进空桶后如果回溯失败，就不必再尝试其他空桶。

这题最坏复杂度仍然指数级，因为本质接近 NP 完全的装箱搜索；面试重点是正确建模和解释剪枝为什么不改变答案。

完整版教学

一、先把问题转成“装桶”

给定 nums = [4,3,2,3,5,2,1]，k = 4，总和是 20，所以每个桶目标和是 5。一个可行划分是：

[5]
[4,1]
[3,2]
[3,2]

这就是把每个数字放到 4 个桶里，要求每个桶最终和都是 5。

数字流：5,4,3,3,2,2,1
桶：    0 0 0 0
目标：  5

二、为什么先做必要性判断

回溯前有两个非常重要的快速判断：

判断	原因
`sum % k != 0`	总和无法平均分成 k 份
`max(nums) > sum / k`	最大元素单独都超过桶容量

例如总和是 22、k=4，每个桶不可能是整数目标和，直接返回 false。如果目标和是 5，但数组里有 8，也必然放不进任何桶。

记忆钩子：先验失败越早判断，回溯树越少展开；装桶题先看总容量和最大物品。

三、两种常见写法：按数字放桶和按桶填数

常见实现有两类：

写法	状态	特点
按数字放桶	第 `index` 个数字放入哪个桶	模板直观，容易写对剪枝
按桶填数	当前桶从哪些未用数字里选	更像组合总和，适合位掩码优化

面试中更推荐先讲“按数字放桶”，因为它和题意最贴近：每个数字必须被分配到一个子集。只要解释清楚桶之间的对称剪枝，就能拿到主要分。

四、为什么要降序排序

如果先放小数，很多分支看起来暂时合法，但后面大数可能放不下，失败发生得很晚。降序排序让大数先占坑，越界越早暴露。

升序：1,2,2,3,3,4,5  -> 先产生很多小数排列
降序：5,4,3,3,2,2,1  -> 5 只能单独成桶，4 必须配 1

排序不改变答案，因为最终只是划分集合，不关心处理顺序；它只改变搜索树展开顺序。

五、对称剪枝为什么安全

桶没有名字。当前桶和为 [2, 2, 0, 0] 时，把数字 3 放入第一个和为 2 的桶，得到 [5,2,0,0]；放入第二个和为 2 的桶，得到 [2,5,0,0]。这两个状态只是桶顺序不同，本质等价。

所以在同一层中，如果某个桶的当前和已经尝试过，就可以跳过后面相同和的桶。

buckets[j] == buckets[j - 1] 这类状态等价

实际代码中常用 if (j > 0 && buckets[j] == buckets[j - 1]) continue;，或者用集合记录本层试过的桶和。

六、代码模板

boolean canPartitionKSubsets(int[] nums, int k) {
    int sum = 0;
    for (int x : nums) sum += x;
    if (sum % k != 0) return false;
    int target = sum / k;
    Arrays.sort(nums);
    reverse(nums);
    if (nums[0] > target) return false;
    return dfs(nums, 0, new int[k], target);
}

boolean dfs(int[] nums, int index, int[] buckets, int target) {
    if (index == nums.length) return true;
    int x = nums[index];
    Set<Integer> tried = new HashSet<>();
    for (int j = 0; j < buckets.length; j++) {
        if (buckets[j] + x > target) continue;
        if (tried.contains(buckets[j])) continue;
        tried.add(buckets[j]);

        buckets[j] += x;
        if (dfs(nums, index + 1, buckets, target)) return true;
        buckets[j] -= x;

        if (buckets[j] == 0) break;
    }
    return false;
}

这里 if (buckets[j] == 0) break 的意思是：放进一个空桶后都失败，放进另一个空桶只是换了桶名字，也会失败。

七、常见误区与追问

误区：只要总和能整除就一定能划分。 整除只是必要条件，不是充分条件，还要通过搜索确认。
误区：桶有编号，所有桶排列都要试。 桶之间是对称的，同和桶和空桶都能剪掉重复状态。
误区：不排序也一样快。 正确性一样，但降序排序能让超容量失败更早出现。
追问：为什么这是指数级问题？ 每个元素理论上可放入多个桶，状态组合数量随 n 快速增长，剪枝只能改善实际表现。
追问：能不能用状态压缩 DP？ 可以用位掩码记录已选元素和当前桶内和，复杂度约 O(n * 2^n)。
追问：为什么空桶失败可以 break？ 所有空桶状态完全等价，换一个空桶不会产生新信息。

八、加强记忆

划分 K 个等和子集要记成“装桶 + 对称剪枝”：先用总和和最大数做必要性判断，再把数字降序放入桶。每次选择一个数字，尝试放进不超目标和的桶；如果桶当前和相同，代表状态等价，可以跳过；如果放进空桶都失败，其他空桶也不用试。面试时能把“桶无名、状态对称”讲清楚，比只背代码更关键。

简化版

详细版