划分为 k 个相等的子集 图解题解

这道题到底在问什么

nums

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

k

4

输出

true

一种分法

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

先想最直接的笨办法

拿起 4（还在 path 里没落桶），从桶0 开始试：桶0 已经是 5，5+4=9 超过 target=5，放不下，跳过桶0。换下一个桶试试。（动画第 10 步）

最优解：一步一步想明白

1. 3总和除以 k 就是每个桶该装的数。如果总和不能被 k 整除，连试都不用试，直接 false——比如 20÷3 除不尽，怎么分都不可能均等。本题 20÷4=5，能整除，继续。
2. 4最直白的想法：每个数有 k 种去处，n 个数就有 k 的 n 次方种摆法，全摆完再逐桶检查。能跑但爆炸式增长——其实可以边放边查、不合适立刻回头，这就是回溯。
3. 5按顺序处理每个数：试着把它放进某个桶，只要放进去后这桶不超过 target 就放，然后递归去放下一个数；如果后面走不通，就把这个数从桶里拿回来，换下一个桶试。选→递归→撤销，回溯三件套。
4. 6提速关键：① 把数从大到小排，大数难安置、早放早暴露死路；② 如果某个数放进一个空桶后整体失败了，那放进另一个同样空的桶结果完全一样（桶之间对称），直接停、不重复试空桶。下面用 nums 排序后 [5,4,3,3,2,2,1]、target=5 走一遍。
5. 7待放 [5,4,3,3,2,2,1]，每桶目标 5从大到小排好序：[5,4,3,3,2,2,1]。下面「已收集的结果 res」这一排的 4 个 [ ] 就是 4 个桶，每个要装到和为 5。上面「可选数字」逐个变灰表示已放进某个桶。开始逐个安置。
6. 8当前数 5，从桶0 开始试拿起第一个数 5（上面那格亮起，「当前路径 path」也显示它），它还没进任何桶。从桶0 开始逐个试：哪个桶加上 5 不超过 target=5 就放进去。
7. 9桶0: 0+5=5 ≤ 5 ✓ 放入5 放进空桶0：0+5=5 正好等于 target，桶0 直接装满，5 从 path 落进桶0、上面那格变灰=已用。接着处理下一个数 4。
8. 10桶0: 5+4=9 > 5 ✗ 跳过拿起 4（还在 path 里没落桶），从桶0 开始试：桶0 已经是 5，5+4=9 超过 target=5，放不下，跳过桶0。换下一个桶试试。
9. 11桶1: 0+4=4 ≤ 5 ✓ 放入桶1 是空的，0+4=4 ≤ 5 放得下，4 落进桶1，上面变灰。桶1 现在还差 1 才满。继续放下一个 3。
10. 12当前数 3，从桶0 开始试拿起第一个 3（还在 path 里）。桶0 满了放不下；桶1 是 4，4+3=7 也超了。前两个桶都不行，继续往后试空桶2。
11. 13桶2: 0+3=3 ≤ 5 ✓ 放入桶2 空的，0+3=3 放得下，3 落进桶2。桶2 还差 2。第一个 3 安置好，处理第二个 3。
12. 14桶0满/桶1超(7)/桶2超(6) 都不行拿起第二个 3。桶0 满、桶1 是4(4+3=7超)、桶2 是3(3+3=6超)都塞不进。只剩空桶3 了。
13. 15桶3: 0+3=3 ≤ 5 ✓ 放入落到空桶3，0+3=3。四个桶现在分别是 5 / 4 / 3 / 3。开始处理两个 2。
14. 16桶0满 ✗ · 桶1: 4+2=6>5 ✗拿起第一个 2。桶0 满了；桶1 是 4，4+2=6 超过 5。注意:桶1 差的是 1、不是 2，2 进不去。继续看桶2。
15. 17桶2: 3+2=5 ✓ 正好满桶2 是 3，3+2=5 正好装满！桶2 现在是 [3,2]=5。已经有桶0、桶2 两个满桶了。处理第二个 2。
16. 18桶0满/桶1超/桶2刚满 都不行拿起第二个 2。桶0 满、桶1(4+2=6)超、桶2 刚满，前三个都进不去。只剩桶3 可试。
17. 19桶3: 3+2=5 ✓ 正好满落进桶3：3+2=5 又满了。现在三个满桶 + 桶1 还差 1。只剩最后一个数 1。
18. 20桶0: 5 满 ✗ 跳过拿起最后一个数 1。先试桶0：已经是 5 满了，放不下，跳过。看桶1——它正好差 1。
19. 21桶1: 4+1=5 ✓ 全部满 → true桶1 是 4，4+1=5 正好补满！所有数都用完、四个桶全是 5。返回 true。这次运气好一路顺到底，没触发回溯。
20. 22[5] [4,1] [3,2] [3,2]，每桶和=5 ✓最终分法：[5] · [4,1] · [3,2] · [3,2]，四组和都等于 target=5。所有数恰好用一次。划分成功！
21. 23示意:把 2 放进桶2 → 后续凑不满 ✗回溯机制实演（示意）:本例恰好一路顺、没真触发回溯，这里单独演一下「走死了怎么办」。假设把某个 2 放进桶2 后，剩下的数怎么都凑不满其它桶——那这一步就是死路。
22. 24buckets[2] -= 2，2 退回 path走死就撤销:把刚放进桶2 的 2 拿回来(代码里 buckets[j] -= nums[i])，桶2 退回到 [3]、2 重新回到 path 待分配。这就是回溯的「悔棋」。
23. 25改放桶3: 3+2=5 ✓撤销后换下一个桶继续试。回溯就是这样「放→走不通→拿回来→换一个」，把所有摆法不重不漏地试遍——这正是它能给出确定答案的底气。
24. 28本题视角是「站在每个数的角度，给它找桶」而不是「站在桶的角度凑数」——这样递归深度恰好是 n、每层只决定一个数的去向，配合 target 这道「放不放得下」的门，逻辑最清爽。
25. 31不排序 → 大数 5 拖到最后才发现塞不下负例：如果不排序、按原顺序放，小数先把桶填得七零八落，等最后才轮到大数 5 时常发现哪个桶都塞不下、被迫大量回溯。先把大数排到前面，难安置的早安置，能极大减少回溯次数。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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)

class Solution {
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int total = 0;
        for (int x : nums) total += x;
        if (total % k != 0) return false;
        int target = total / k;
        sort(nums.rbegin(), nums.rend());      // 从大到小
        if (nums[0] > target) return false;
        int n = nums.size();
        vector<int> buckets(k, 0);
        function<bool(int)> dfs = [&](int i) {
            if (i == n) return true;
            for (int j = 0; j < k; ++j) {
                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);
    }
};

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int total = 0;
        for (int x : nums) total += x;
        if (total % k != 0) return false;
        int target = total / k;
        Arrays.sort(nums);
        reverse(nums);                         // 从大到小
        if (nums[0] > target) return false;
        int[] buckets = new int[k];
        return dfs(nums, 0, buckets, target);
    }
    private boolean dfs(int[] nums, int i, int[] buckets, int target) {
        if (i == nums.length) return true;
        for (int j = 0; j < buckets.length; ++j) {
            if (buckets[j] + nums[i] <= target) {
                buckets[j] += nums[i];
                if (dfs(nums, i + 1, buckets, target)) return true;
                buckets[j] -= nums[i];             // 撤销
            }
            if (buckets[j] == 0) break;            // 空桶剪枝
        }
        return false;
    }
    private void reverse(int[] a) {
        for (int x = 0, y = a.length - 1; x < y; ++x, --y) {
            int t = a[x]; a[x] = a[y]; a[y] = t;
        }
    }
}

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

复杂度

面试官可能追问