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

import java.util.*;


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

    private static boolean dfs(int[] w,int[] a,int pos,int num){
        if(pos == w.length){
            return true ; 
        }
        for(int i = 0;i < 3;i++){
            if(a[i] + w[pos] > num){
                continue ; 
            }
            a[i] += w[pos] ; 
            if(dfs(w,a,pos+1,num)){
                return true ; 
            }
            a[i] -= w[pos] ; 
        }
        return false ; 
    }



}

dfs遍历