LeetCode698、划分K个相等的子集（回溯解法）

题目描述

给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。

示例 1： 输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4 输出： True 说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。 示例 2: 输入: nums = [1,2,3,4], k = 3 输出: False

提示： 1 <= k <= len(nums) <= 16 0 < nums[i] < 10000 每个元素的频率在 [1,4] 范围内

题目解析

好的，没问题！我是 AlgoMooc 的算法老师，很高兴能带你一起搞定这道题。别担心，这道题听起来有点绕，但跟着我的思路，用生活里的例子来理解，你会发现它其实很亲切。

我们一步一步来。

题目在说什么

简单来说，就是给你一堆数字，比如 [4, 3, 2, 3, 5, 2, 1]，和一个数字 k=4。你要判断能不能把这堆数字，平均分成 k 组，并且每一组数字加起来的总和都一样。

你可以想象成，你是一个班级的班主任，手上有一些糖果（数字），你要把这些糖果平均分给 k 个小组，每个小组分到的糖果总数必须一样多。题目问的就是，能不能做到？

比如示例1，就可以分成 (5)，(1,4)，(2,3)，(2,3)，每组加起来都是5，所以答案是 True。

而示例2，[1,2,3,4] 总和是10，要分给 k=3 组，10除以3除不尽，所以肯定不行，答案是 False。

思路是怎么来的

1. 先做“不可能”的排除

想象一下，如果你要分糖果，什么情况下是绝对不可能平均分的？

• 情况一：糖果总数不能被小组数整除。 比如10颗糖分给3个组，每个组必须分到一样多，但10除以3除不尽，那就不可能。所以，我们第一步就是算总和 total，看它能不能被 k 整除。不能的话，直接说“不行”，省事。

• 情况二：有一颗糖太大了，比每个小组该分到的总数还大。 比如每组应该分到5颗糖，但有一颗糖是6颗，那这颗糖放哪个组都会超，所以也不可能。所以，我们还要看看最大的那颗糖，是不是比每个小组的目标总和 per 还大。

2. 核心思路：像分糖果一样“回溯”

如果上面的排除都没问题，那我们就开始尝试分。怎么分呢？最笨但最可靠的方法就是：一个一个试。

我们把问题想象成：有 k 个空桶（代表k个小组），每个桶的目标是装总和为 per 的糖果。我们手里有一堆糖果（数字），我们要把糖果一颗一颗地放进桶里。

• 第一步：从最大的糖果开始。 为什么？因为大的糖果比较“笨重”，它放哪儿基本就定下来了，不容易再动。比如你有一个5斤的大西瓜，你肯定先想好把它放哪个篮子里。而小糖果（比如1、2）很灵活，可以最后用来“填缝”。所以，我们把数字从大到小排序，先处理大的。

• 第二步：开始“试”。 我们拿起第一颗最大的糖果，尝试把它放进第一个桶。放进去之后，这个桶的当前总和就增加了。然后，我们拿起第二颗糖果，再尝试放进第一个桶……如果放进去之后，这个桶的总和没有超过目标值 per，那就继续放下一颗。如果超过了，那这颗糖果就不能放这个桶了，我们得把它拿出来，试试放到下一个桶。

• 第三步：发现走不通就“回头”。 这就是“回溯”的精髓。比如，你试了很多种放法，发现最后总有一颗糖果没地方放，或者某个桶的总和无论如何都凑不够 per。那说明你之前某个步骤的选择是错的。这时候，你就需要回到上一步，把刚才放进去的那颗糖果拿出来，换个桶试试。这个过程就像走迷宫，发现是死胡同，就退回去，换个路口再走。

• 第四步：找到答案就停。 如果你把所有糖果都成功放进了桶里，并且每个桶的总和都刚好等于 per，那就成功了！我们用一个叫 ans 的“小旗子”来标记，一旦找到答案，就立刻停止所有尝试。

3. 一个小技巧：剪枝

回溯虽然能解决问题，但可能会很慢，因为它会尝试所有可能。为了让它跑得快一点，我们得学会“剪枝”，就是把一些明显没必要的尝试直接砍掉。

比如，你尝试把一颗糖果放进第一个桶，发现不行（会超），然后你准备把它放进第二个桶。但是，如果第二个桶当前的糖果总和和第一个桶一模一样，那放进去的结果肯定也一样（都会超），所以就没必要再试了。这就是代码里 if (j != 0 && group[j] == group[j - 1]) 这句的作用。

代码逐步拆解

现在，我们对照着代码，一步步看它是怎么实现这个思路的。

public class Solution {
    private boolean ans = false; // 1. 定义一个小旗子，记录我们是否找到了答案

    public void dfs(int[] group, int i, int[] nums, int per, int n, int k) {
        // 2. 递归终止条件：如果所有糖果都分完了 (i == n)，或者已经找到答案了 (ans)
        if (i == n || ans) {
            ans = true; // 把旗子举起来，表示找到了
            return;     // 立刻返回，不再继续
        }

        // 3. 横向遍历：尝试把第 i 颗糖果放进 k 个不同的桶里
        for (int j = 0; j < k; j++) {
            // 4. 剪枝：如果当前桶的和 和 前一个桶的和一样，就不用试了（结果一样）
            if (j != 0 && group[j] == group[j - 1]) {
                continue;
            }

            // 5. 状态更新：把第 i 颗糖果放进第 j 个桶
            group[j] += nums[i];

            // 6. 检查：放进这个桶后，这个桶的总和有没有超过目标 per？
            if (group[j] <= per) {
                // 没超过，就继续处理下一颗糖果（第 i+1 颗）