跳到主要内容

LeetCode 698. 划分为 k 个相等的子集

本节目标

降序放置数字，用容量上界与等价桶剪枝搜索分组方案。

这道题练习搜索与剪枝综合中的分配模型：按顺序处理数字，把每个数字放进一个桶，并利用容量上界与桶的对称性减少重复状态。

查看 LeetCode 原题

题意与约束​

给定正整数数组 nums 和整数 k，判断能否把所有数字划分为 k 个非空子集，使每个子集的元素和相等。每个数字必须恰好使用一次。

若总和不能被 k 整除，显然无解。否则每个子集的目标和固定为 total / k，问题就转化为把数字放入 k 个容量相同的桶。

朴素思路与瓶颈​

对每个数字枚举它属于哪个桶，最坏会形成 k^n 个分配方案。更糟的是，桶没有名字：把第一个数字放入空桶 0 或空桶 1，产生的状态本质相同。若不识别这种对称性，搜索会反复走过等价子树。

排序、容量与对称性​

先把数字降序排列。大数更难安放，让它们先选择可以更早触发“超过目标和”的失败条件。若最大数字已经超过目标和，可以直接返回假。

递归参数 index 表示下一个待放数字，buckets[i] 表示第 i 个桶当前和。对每个桶依次检查：

  1. 放入后超过目标和，跳过；
  2. 本层已经尝试过另一个具有相同当前和的桶，跳过；
  3. 否则放入数字，递归处理下一个，失败后撤销。

当一个数字放入空桶后仍然无法完成，其他空桶与它完全等价，可以直接停止本层枚举。

所有数字都成功放置时，每个桶都不会超过目标，而桶总和又等于全部数字总和，因此每个桶必然恰好达到目标，无须再次逐桶检查。

代码实现​

两种实现都直接维护 k 个桶的当前和，没有使用位掩码动态规划。输入数组先降序排列，函数只处理已经准备好的参数。

C++17
#include <algorithm>
#include <numeric>
#include <vector>

using namespace std;

class Solution {
private:
    bool backtrack(
        const vector<int>& nums,
        int index,
        int target,
        vector<int>& buckets
    ) {
        if (index == static_cast<int>(nums.size())) {
            return true;
        }

        const int value = nums[index];
        int previousCapacity = -1;
        for (int& bucket : buckets) {
            if (bucket == previousCapacity || bucket + value > target) {
                continue;
            }

            previousCapacity = bucket;
            bucket += value;
            if (backtrack(nums, index + 1, target, buckets)) {
                return true;
            }
            bucket -= value;

            if (bucket == 0) {
                break;
            }
        }

        return false;
    }

public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        const int total = accumulate(nums.begin(), nums.end(), 0);
        if (total % k != 0) {
            return false;
        }

        const int target = total / k;
        sort(nums.rbegin(), nums.rend());
        if (nums.front() > target) {
            return false;
        }

        vector<int> buckets(k, 0);
        return backtrack(nums, 0, target, buckets);
    }
};

复杂度分析​

设数组长度为 n。

  • 每个数字最坏尝试 k 个桶，时间复杂度上界为 O(k^n)；降序、容量与等价桶剪枝会显著缩小实际搜索树。
  • 排序需要 O(n log n) 时间；桶数组为 O(k)，递归栈为 O(n)。

易错点​

  • 忘记检查总和是否能被 k 整除。
  • 没有降序排序，使容量剪枝很晚才生效。
  • 用“数字值相同”代替“桶当前和相同”判断等价状态。
  • 放入失败后没有恢复桶和。
  • 在空桶失败后仍继续尝试其他空桶，重复搜索对称方案。

模式迁移​

装载、分组和小规模调度问题常能写成“物品依次进入容器”的回溯。优化顺序通常是：先处理约束最强的物品，再检查容量上界，最后合并等价容器。若数据规模需要位掩码动态规划，那属于另一条进阶路线，不是本题基础模板的重点。