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

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