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

考察的知识点：动态规划；

解答方法分析：

1. 计算所有奶牛的总体重量 totalWeight，并检查它是否能够被3整除。如果不能被3整除，那么无法将奶牛分成三组，直接返回 false。
2. 确定每组的目标体重 targetWeight，即 totalWeight / 3。
3. 定义一个长度为3的数组 groupSums，用于记录每组的体重和。初始时，所有组的和都为0。
4. 调用回溯函数 backtrack(weights, 0, groupSums, targetWeight)，尝试将奶牛分到三组中的某一组中。
5. 在回溯函数中，首先查是否所有奶牛已经分完，即 index == weights.length。如果是，则检查每组的体重和是否相等，如果相等则返回 true，否则返回 false。
6. 如果奶牛还没有分完我们尝试将当前奶牛分到三组中的某一组中。遍历 0 到 2 的所有组，并检查将当前奶牛加入该组后，组的体重和是否小于等于目标体重 targetWeight。如果是，则加入该组，并继续递归调用回溯函数，看能否成功将剩余的奶牛分到三组中。如果递归调用返回 true，则表示成功分组，返回 true。如果递归调用返回 false，则表示当前方式不可行，需要回溯，将当前奶牛从该组中移除，尝试其他组的分配方式。
7. 如果所有组的分配方式都被尝试过后，仍然无法成功分组，则返回 false。

所用编程语言：C++；

完整编程代码：↓

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param weights int整型vector
     * @return bool布尔型
     */
    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;
    }
    bool canPartitionII(vector<int>& weights) {
        int n = weights.size();
        int totalWeight = 0;
        for (int weight : weights) {
            totalWeight += weight;
        }
        if (totalWeight % 3 != 0) {
            return false;
        }
        int Weight = totalWeight / 3;
        vector<int> groupSums(3, 0);
        return backtrack(weights, 0, groupSums, Weight);
    }
};