集合划分变题「未给定具体划分大小」

5289. 公平分发饼干

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

473. 火柴拼正方形

今天比赛中有一个题目 公平分发饼干，和「集合划分问题」相似度高达 90%，但是脑子一时没有转过弯，比赛的时候没有写出来，特意总结一波！！

关于集合划分问题详细分析，可见 经典回溯算法：集合划分问题

区别

先来说一下本问题和「集合划分问题」的区别！

对于「集合划分问题」，题目中给出了每个集合可容纳的大小，可以根据是否溢出来决定是否选择桶

但是对于本问题，没有给出每个集合可容纳的大小，只是让我们求所有划分中最大值的最小值 (有点绕！！)

所以一时之间不知道如何处理，还是太菜了，不知道如何灵活运用！！😭😭😭

思路

我们使用「球视角」的思路，即：让每个球来选择桶，当最后一个球完成选择，则到达「结束条件」

那我们可以从什么角度剪枝呢？

剪枝一：为了保证每个桶中至少有一个球，所以如果还剩n个空桶，但剩余球的数量小于n，可直接跳过

剪枝二：对于第一个球，任意放到某个桶中的效果都是一样的，所以我们规定放到第一个桶中

剪枝三：如果桶的大小已经超过了最小值，则肯定不是最优解，可直接跳过

剪枝四：如果当前桶和上一个桶内的元素和相等，则跳过。原因：如果元素和相等，那么当前球选择上一个桶和选择当前桶可以得到的结果是一致的

这里还有一个小技巧：对球排序，优先让值更大的球做选择，这样可以增加回溯的命中率

代码实现

private int ans = Integer.MAX_VALUE;
public int distributeCookies(int[] cookies, int k) {
    // 排序
    Arrays.sort(cookies);
    for (int lo = 0, hi = cookies.length - 1; lo <= hi; lo++, hi--) {
        int t = cookies[lo];
        cookies[lo] = cookies[hi];
        cookies[hi] = t;
    }
    backtrack(cookies, 0, new int[k]);
    return ans;
}
private void backtrack(int[] cookies, int start, int[] bucket) {
    if (start == cookies.length) {
        // 记录一次划分中的最大值
        int max = 0;
        for (int b : bucket) {
            max = Math.max(max, b);
        }
        // 记录所有划分中最大值的最小值 (有点绕！！)
        ans = Math.min(ans, max);
        return ;
    }
    // 计算空桶数量
    int empty = 0;
    for (int b : bucket) {
        if (b == 0) empty++;
    }
    // 剪枝一
    if (empty > cookies.length - start) return ;
    for (int i = 0; i < bucket.length; i++) {
        // 剪枝二
        if (i > 0 && start == 0) return ;
        // 剪枝三
        if (i > 0 && bucket[i] == bucket[i - 1]) continue;
        // 剪枝四
        if (bucket[i] + cookies[start] > ans) continue;
        bucket[i] += cookies[start];
        // 处理下一个球
        backtrack(cookies, start + 1, bucket);
        bucket[i] -= cookies[start];
    }
}

贴一下执行时间：