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

import java.util.*;


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

    public boolean search(int[] weights, int index, int a, int b, int c) {
        if (index==weights.length && a == b && b == c) {
            return true;
        }else if(index==weights.length){
            return false;
        } 
        return search(weights, index + 1, a + weights[index], b, c)
               || search(weights, index + 1, a , b + weights[index], c)
               || search(weights, index + 1, a, b, c + weights[index]);
    }


}

本题我采用的是递归算法，所用编程语言是java。

我考虑使用三个桶往三个方向进行深度遍历，只要有一个方向返回true则整个深度遍历过程返回true，否则返回false。