题解 | #农场的奶牛分组II#
农场的奶牛分组II
https://www.nowcoder.com/practice/ae745225d12f44ca9e84486d051edbfa
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。