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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param weights int整型一维数组
     * @return bool布尔型
     */
    public boolean canPartitionII (int[] weights) {
        // write code here
        int n = weights.length;
        int totalWeight = 0;
        for (int weight : weights) {
            totalWeight += weight;
        }

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

        // 目标每组体重
        int targetWeight = totalWeight / 3;
        int[] groupSums = new int[3];

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

// 回溯函数
    private boolean backtrack(int[] weights, int index, int[] groupSums,
                              int targetWeight) {
        // 所有奶牛都已分完，检查三组的体重和是否相等
        if (index == weights.length) {
            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;
    }
}

编程语言是Java。

该题考察的知识点是回溯算法

代码的文字解释如下：首先计算所有奶牛的总体重，如果总体重不能被3整除，则无法分成三组，直接返回false。然后计算目标每组体重targetWeight，即总体重除以3。使用一个长度为3的数组groupSums来保存每组的体重和，初始值为0。调用回溯函数backtrack来进行尝试分组，并返回分组是否成功的结果。

回溯函数backtrack递归地遍历每个奶牛，并尝试将其分到三组中的某一组，判断加入后该组的体重和是否小于等于targetWeight。如果满足条件，则将奶牛加入该组中，并继续递归地处理下一个奶牛。如果递归返回true，表示成功找到了一种分组方式，直接返回true。如果递归返回false，表示该分组方式不合适，需要将奶牛从当前组中移出，继续尝试其他分组方式。最终如果所有奶牛都已分完，检查三组的体重和是否相等，如果相等则返回true，否则返回false。