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

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;
        }

        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。

该题考察的知识点：递归与回溯，代码使用递归和回溯方法来尝试将一组物品分成三个相等的子集，以满足特定条件。

代码的文字解释：

1. 计算总体重：遍历整数数组 weights 中的每个元素，累加得到总体重 totalWeight。
2. 判断总体重能否被3整除：如果总体重不能被3整除，就无法将元素分成三个相等的子集，直接返回 false。
3. 计算目标每组体重：将总体重除以 3，得到目标每组体重 targetWeight。
4. 创建数组来记录每个组的当前体重和：使用 int[] groupSums 来存储每个组的当前体重和，长度为 3。
5. 调用回溯函数：调用 backtrack 方法，传入初始参数进行递归搜索。
6. 回溯函数：private boolean backtrack(int[] weights, int index, int[] groupSums, int targetWeight)，这个函数用来进行递归和回溯，尝试将每个元素分配到三个不同的组中，检查是否能满足特定条件。基础情况：如果已经将所有元素分配完毕（index == weights.length），则检查三个组的体重和是否相等，如果相等则返回 true。递归尝试：尝试将当前元素分配到三个不同的组中，如果满足条件则继续递归。回溯：如果分配不满足条件，则回溯，尝试其他可能性，保持组的体重和不变。