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

农场的奶牛分组

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

全部评论

相关推荐

点赞 评论 收藏
分享
07-02 22:46
门头沟学院 Java
码农索隆:hr:“管你投没投,先挂了再说”
点赞 评论 收藏
分享
写不来代码的小黑:这么小的城市能有做it的公司也不容易
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务