题解 | #农场的奶牛分组#
农场的奶牛分组
https://www.nowcoder.com/practice/bdb90a97a15d42f989e406080d88bed9
import java.util.*; public class Solution { /** 足以应付ACM模式的递归,使用全局变量,最终效率不输一般的动态规划 */ int[] weight = new int[201]; int he1 = 0; int he2 = 0; int index = 0; public boolean canPartition (int[] weights) { int sum = Arrays.stream(weights).sum(); // 无法分为两组 if (weights.length < 2 || sum % 2 != 0) { return false; } weight = weights; return dfs(he1, he2, index); } public boolean dfs(int h1, int h2, int index) { if (index == weight.length) { if (he1 == he2) { return true; } else { return false; } } return dfs(he1 + weight[index], he2, index + 1) || dfs(he1, he2 + weight[index], index + 1); } }