题目描述
思路解析
一句话答案：LeetCode 2305 公平分发饼干用回溯：逐包试发给每个孩子、发完撤回换人再试，配「超标就剪」「空手只试一个」两把剪枝；贪心分包会错，只能穷举本质不同的分法取最小，时间 O(kⁿ)、空间 O(n+k)。
不公平程度，为什么只看拿最多的孩子
cookies[i] 是第 i 包的饼干数，所有包要分给 k 个孩子，每包必须整包给同一个人。一种分法的不公平程度＝拿最多的孩子的总数，要在所有分法里把它压到最小。示例 cookies=[8,15,10,20,8]、k 为 2：[20,10] 给一人共 30，[15,8,8] 给另一人共 31，不公平程度 31，已是最小。
kⁿ 条分法，硬试和贪心各卡在哪
每一包都有 k 个去处，n 包连着选就是 kⁿ 条分法，包数一多根本试不完。贪心也靠不住：把包从大到小排、每包发给当前拿最少的孩子，[20,15,10,8,8] 会分成 20+8=28 和 15+10+8=33，得 33；可最优是 31——10 一旦跟着 15 走，后面怎么补都回不到 31。
逐包试发再撤回，回溯怎么把分法数完
回溯就是一条路走到底、不行退一步换条路的穷举法。开 cnt[j] 记孩子 j 当前拿到的总数，处理某一包时轮流试发：cnt[j] 加上这包，用同一套流程接着发下一包（自己套自己，这就是递归），发完回来把这包减掉，换下一个孩子再试。所有包发出去就走完一条分法，用此刻最大的 cnt 更新最优 ans。加了又减的撤回，保证各分支互不串账。
两把剪刀砍掉的分支，最优解为什么漏不掉
剪枝，就是把注定不会更好的分支整支跳过。第一把：cnt[j] 加上这包后不小于 ans 就不发——这条分支的最大值只会更高，绝无机会刷新答案。第二把：孩子 j 和前一个孩子手里一样多就跳过——这包给谁往后完全对称，只试前一个，砍掉的全是重复分法。
把 cookies 从大到小排序也为剪刀服务：大包先发 cnt 涨得快，第一把剪刀更早够到 ans；排序不改答案，只把砍的时机提前。
五包饼干分给两人，31 是怎么搜出来的
排好序是 [20,15,10,8,8]。发第一包 20 时两人都空手，第二把剪刀只放行孩子一。先一路全发给孩子一得 61，ans 记下 61；退一步把最后一包 8 改给孩子二，得 53；再退再换，ans 一路被压成 45、43、35 三个中间值，各是某条更优分法搜到底时较重那人的总数。
走到 20、10 归孩子一（共 30），15、8 归孩子二（共 23）这条：最后一包 8 发孩子一是 38，不小于 35 被剪，改发孩子二得 23+8=31，两人 30 和 31，ans 刷成 31。之后出现两人 28 和 25、只剩一包 8 的局面：发孩子一 36、发孩子二 33，都不小于 31，两边全剪，走不到头。全部试完，最小不公平程度就是 31。
所有包发完直接改 ans，为什么不会把答案改坏
参考代码发完所有包时直接写 ans = max(cnt)，连比较都不做，靠的正是第一把剪刀：每个值塞进 cnt 时都验过，能走到头就说明此刻 max(cnt) 不超过当前 ans，赋值只会把 ans 改小或持平。时间上界 O(kⁿ)（大 O 是衡量规模对计算量放大倍数的记法），空间 O(n+k)。k 等于包数时每人恰好分一包，答案就是最大那包。最大的一包总得有人整包拿走，答案永远不会低于 max(cookies)。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这套「逐包试着发、发完更新答案、超标就剪、重复空桶就剪」，下面每一帧都在套它。
开局：孩子1、孩子2 手里都是 0 块饼干。右边是四包饼干，已经从大到小排成 6、4、3、1。我们要把每一包整包发出去，让最后拿得最多的孩子尽量少。
把这包 6 发给 孩子1，它从 0 变成 6，接着发下一包。
把这包 4 发给 孩子1，它从 6 变成 10，接着发下一包。
把这包 3 发给 孩子1，它从 10 变成 13，接着发下一包。
把这包 1 发给 孩子1，它从 13 变成 14，接着发下一包。
四包都发完了，孩子1有 14、孩子2有 0，这条分法里最多的是 14。比之前记的最优还小，答案刷新成 14。
换一种：把这包 1 改发给 孩子2，它从 0 变成 1，还没到已知最优 14，可以往下走。
四包都发完了，孩子1有 13、孩子2有 1，这条分法里最多的是 13。比之前记的最优还小，答案刷新成 13。
换一种：把这包 3 改发给 孩子2，它从 0 变成 3，还没到已知最优 13，可以往下走。
把这包 1 发给 孩子1，它从 10 变成 11，还没到已知最优 13，可以往下走。
四包都发完了，孩子1有 11、孩子2有 3，这条分法里最多的是 11。比之前记的最优还小，答案刷新成 11。
换一种：把这包 1 改发给 孩子2，它从 3 变成 4，还没到已知最优 11，可以往下走。
四包都发完了，孩子1有 10、孩子2有 4，这条分法里最多的是 10。比之前记的最优还小，答案刷新成 10。
换一种：把这包 4 改发给 孩子2，它从 0 变成 4，还没到已知最优 10，可以往下走。
把这包 3 发给 孩子1，它从 6 变成 9，还没到已知最优 10，可以往下走。
想把这包 1 发给 孩子1，可它现在有 9，加上去是 10，已经不小于已知最优 10，这条路不可能更好，孩子1 标红剪掉。
换一种：把这包 1 改发给 孩子2，它从 4 变成 5，还没到已知最优 10，可以往下走。
四包都发完了，孩子1有 9、孩子2有 5，这条分法里最多的是 9。比之前记的最优还小，答案刷新成 9。
换一种：把这包 3 改发给 孩子2，它从 4 变成 7，还没到已知最优 9，可以往下走。
把这包 1 发给 孩子1，它从 6 变成 7，还没到已知最优 9，可以往下走。
四包都发完了，孩子1有 7、孩子2有 7，这条分法里最多的是 7。比之前记的最优还小，答案刷新成 7。
想把这包 1 发给 孩子2，可它现在有 7，加上去是 8，已经不小于已知最优 7，这条路不可能更好，孩子2 标红剪掉。
孩子2 现在手里 0，和 孩子1 一模一样。这包发给谁效果完全相同，只留前一个就够，孩子2 这条重复分支剪掉。
孩子1 起手的所有发法都试过，孩子2 起手因为和孩子1 完全对称被整支剪掉，回溯把每种本质不同的分法都走遍。最好的一种是 [6,1] 给一人、[4,3] 给另一人，最多 7，答案就是 7。
小规模先手算验证：能平分就平分，但最大的一包永远压着答案的下限。
两个高频追问：可升级到状压 DP，二分答案的判定并不省事。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def distributeCookies(self, cookies: List[int], k: int) -> int: def dfs(i): if i >= len(cookies): nonlocal ans ans = max(cnt) return for j in range(k): if cnt[j] + cookies[i] >= ans or (j and cnt[j] == cnt[j - 1]): continue cnt[j] += cookies[i] dfs(i + 1) cnt[j] -= cookies[i] ans = inf cnt = [0] * k cookies.sort(reverse=True) dfs(0) return ans复杂度
- 时间：O(k^n)，n 包每包试 k 个孩子，是搜索树上界；两把剪刀后实际远少于此
- 空间：O(n + k)，递归深度 O(n) 加上 k 个孩子的计数数组 O(k)
易错点
面试追问把动画讲成自己的话
追问除了回溯，这题还有别的解法吗？
追问能不能二分答案加可行性判定？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
知道秘密的人数
LeetCode 2327 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题