题目描述
思路解析动画文字版
总和除以 k 就是每个桶该装的数。如果总和不能被 k 整除，连试都不用试，直接 false——比如 20÷3 除不尽，怎么分都不可能均等。本题 20÷4=5，能整除，继续。
最直白的想法：每个数有 k 种去处，n 个数就有 k 的 n 次方种摆法，全摆完再逐桶检查。能跑但爆炸式增长——其实可以边放边查、不合适立刻回头，这就是回溯。
按顺序处理每个数：试着把它放进某个桶，只要放进去后这桶不超过 target 就放，然后递归去放下一个数；如果后面走不通，就把这个数从桶里拿回来，换下一个桶试。选→递归→撤销，回溯三件套。
提速关键：① 把数从大到小排，大数难安置、早放早暴露死路；② 如果某个数放进一个空桶后整体失败了，那放进另一个同样空的桶结果完全一样（桶之间对称），直接停、不重复试空桶。下面用 nums 排序后 [5,4,3,3,2,2,1]、target=5 走一遍。
排序后准备 4 个空桶 · target=5：从大到小排好序：[5,4,3,3,2,2,1]。下面「已收集的结果 res」这一排的 4 个 [ ] 就是 4 个桶，每个要装到和为 5。上面「可选数字」逐个变灰表示已放进某个桶。开始逐个安置。
拿起 5 · 给它找桶：拿起第一个数 5（上面那格亮起，「当前路径 path」也显示它），它还没进任何桶。从桶0 开始逐个试：哪个桶加上 5 不超过 target=5 就放进去。
放 5 → 桶0 · 桶0 满了(=5)：5 放进空桶0：0+5=5 正好等于 target，桶0 直接装满，5 从 path 落进桶0、上面那格变灰=已用。接着处理下一个数 4。
拿起 4 · 桶0 已满放不下：拿起 4（还在 path 里没落桶），从桶0 开始试：桶0 已经是 5，5+4=9 超过 target=5，放不下，跳过桶0。换下一个桶试试。
放 4 → 桶1：桶1 是空的，0+4=4 ≤ 5 放得下，4 落进桶1，上面变灰。桶1 现在还差 1 才满。继续放下一个 3。
拿起第一个 3 · 给它找桶：拿起第一个 3（还在 path 里）。桶0 满了放不下；桶1 是 4，4+3=7 也超了。前两个桶都不行，继续往后试空桶2。
放 3 → 桶2：桶2 空的，0+3=3 放得下，3 落进桶2。桶2 还差 2。第一个 3 安置好，处理第二个 3。
拿起第二个 3 · 给它找桶：拿起第二个 3。桶0 满、桶1 是4(4+3=7超)、桶2 是3(3+3=6超)都塞不进。只剩空桶3 了。
放第二个 3 → 桶3：落到空桶3，0+3=3。四个桶现在分别是 5 / 4 / 3 / 3。开始处理两个 2。
拿起第一个 2 · 给它找桶：拿起第一个 2。桶0 满了；桶1 是 4，4+2=6 超过 5。注意:桶1 差的是 1、不是 2，2 进不去。继续看桶2。
放第一个 2 → 桶2 · 桶2 满了：桶2 是 3，3+2=5 正好装满！桶2 现在是 [3,2]=5。已经有桶0、桶2 两个满桶了。处理第二个 2。
拿起第二个 2 · 给它找桶：拿起第二个 2。桶0 满、桶1(4+2=6)超、桶2 刚满，前三个都进不去。只剩桶3 可试。
放第二个 2 → 桶3 · 桶3 满了：落进桶3：3+2=5 又满了。现在三个满桶 + 桶1 还差 1。只剩最后一个数 1。
拿起 1 · 桶0 满放不下：拿起最后一个数 1。先试桶0：已经是 5 满了，放不下，跳过。看桶1——它正好差 1。
放 1 → 桶1 · 桶1 满了！：桶1 是 4，4+1=5 正好补满！所有数都用完、四个桶全是 5。返回 true。这次运气好一路顺到底，没触发回溯。
成果 · 四桶皆 5：最终分法：[5] · [4,1] · [3,2] · [3,2]，四组和都等于 target=5。所有数恰好用一次。划分成功！
回溯机制实演 ① · 假设某数放进桶后走死：回溯机制实演（示意）:本例恰好一路顺、没真触发回溯，这里单独演一下「走死了怎么办」。假设把某个 2 放进桶2 后，剩下的数怎么都凑不满其它桶——那这一步就是死路。
回溯机制实演 ② · 把它从桶里拿回来(撤销)：走死就撤销:把刚放进桶2 的 2 拿回来(代码里 buckets[j] -= nums[i])，桶2 退回到 [3]、2 重新回到 path 待分配。这就是回溯的「悔棋」。
回溯机制实演 ③ · 换下一个桶重试：撤销后换下一个桶继续试。回溯就是这样「放→走不通→拿回来→换一个」，把所有摆法不重不漏地试遍——这正是它能给出确定答案的底气。
本题视角是「站在每个数的角度，给它找桶」而不是「站在桶的角度凑数」——这样递归深度恰好是 n、每层只决定一个数的去向，配合 target 这道「放不放得下」的门，逻辑最清爽。
易错实演 · 忘了从大到小排序：负例：如果不排序、按原顺序放，小数先把桶填得七零八落，等最后才轮到大数 5 时常发现哪个桶都塞不下、被迫大量回溯。先把大数排到前面，难安置的早安置，能极大减少回溯次数。
边界三连：整除是第一道闸；k 大于元素个数必然有桶空着也不行。回溯天然处理这些边界——搜不到就是 false。
面试常把本题、LC416、状态压缩 DP 串起来考，核心是「分组等和」这一类问题的不同解法层次。
参考代码
class Solution: def canPartitionKSubsets(self, nums, k): total = sum(nums) if total % k != 0: return False target = total // k nums.sort(reverse=True) # 从大到小 if nums[0] > target: return False n = len(nums) buckets = [0] * k def dfs(i): if i == n: return True # 数全放完 → 成功 for j in range(k): if buckets[j] + nums[i] <= target: buckets[j] += nums[i] if dfs(i + 1): return True buckets[j] -= nums[i] # 撤销 if buckets[j] == 0: break # 空桶剪枝 return False return dfs(0)复杂度
- 时间复杂度：O(k · 2^n)，最坏每个数试 k 个桶、状态空间约 2^n；剪枝后实际远小于此
- 空间复杂度：O(n)，递归深度最多 n（每层放一个数），加 k 个桶计数
可套用的代码模板
骨架记牢：按元素递归、每层把当前元素试着塞进每个容器、塞不通就撤销换下一个。所有「把元素分配进若干等价容器」的题都套这个模板。
模板
def dfs(i): if i == n: return True # 全分配完 for j in range(k): # 试每个容器 if 放得下(j, nums[i]): 放入(j, nums[i]) if dfs(i + 1): return True 取出(j, nums[i]) # 撤销 if 容器j为空: break # 空容器等价剪枝 return False易错点
面试追问把动画讲成自己的话
追问和「分割等和子集」(LC416) 有什么关系？
追问为什么用「按数找桶」而不是「按桶凑数」？
追问数据规模更大时还能怎么优化？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
解数独
LeetCode 37 · 困难 · 沿着 回溯套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题