题解 | #农场的奶牛分组II#

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

回溯算法，递归

题目解答方法的文字分析

这道题目要求将一群奶牛分成三组，使得三组奶牛的体重和相等。我们可以使用回溯算法来解决这个问题。

具体解答步骤如下：

1. 首先，计算所有奶牛的体重和 totalWeight。
2. 如果 totalWeight 不能被3整除，说明无法分成三组，直接返回false。
3. 创建一个大小为3的数组 groupSums，用来存储三组奶牛的体重和，初始化为0。
4. 调用回溯函数 backtrack()，从第一个奶牛开始尝试将其分到三组中的某一组，每次分组时更新 groupSums 数组，并继续尝试下一个奶牛。
5. 在回溯函数中，如果当前组的体重和等于 targetWeight（即 totalWeight/3），则递归尝试分下一组；如果当前组的体重和超过 targetWeight，则回溯到上一个奶牛重新尝试其他分组方案。

本题解析所用的编程语言

C++

完整且正确的编程代码

#include <vector>

using namespace std;

class Solution {
public:
    bool canPartitionII(vector<int>& weights) {
        int n = weights.size();
        int totalWeight = 0;
        for (int weight : weights) {
            totalWeight += weight;
        }

        // 如果总体重不能被3整除，无法分成三组，直接返回false
        if (totalWeight % 3 != 0) {
            return false;
        }

        // 目标每组体重
        int targetWeight = totalWeight / 3;
        vector<int> groupSums(3, 0);

        // 调用回溯函数进行尝试分组
        return backtrack(weights, 0, groupSums, targetWeight);
    }

private:
    // 回溯函数
    bool backtrack(vector<int>& weights, int index, vector<int>& groupSums, int targetWeight) {
        // 所有奶牛都已分完，检查三组的体重和是否相等
        if (index == weights.size()) {
            return groupSums[0] == targetWeight && groupSums[1] == targetWeight && groupSums[2] == targetWeight;
        }

        // 尝试将当前奶牛分到三组中的某一组
        for (int i = 0; i < 3; ++i) {
            if (groupSums[i] + weights[index] <= targetWeight) {
                groupSums[i] += weights[index];
                if (backtrack(weights, index + 1, groupSums, targetWeight)) {
                    return true;
                }
                groupSums[i] -= weights[index];
            }
        }

        return false;
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！