leetcode698

n个数字放入k个桶,每个桶总和相等;
n<=16

暴力回溯+减枝
‘’’
class Solution {
public boolean canPartitionKSubsets(int[] nums, int k) {
int sum = 0;
for(int num:nums){
sum += num;
}
int av = sum/k;
if (sum % k !=0){
return false;
}
int[] ksum = new int[k];
for(int i=0;i<k;i++){
ksum[i] = 0;
}
for(int num:nums){
if (num>av){
return false;
}
}
return dfs(0,k,ksum,nums,av);
}

public boolean dfs(int i,int k,int[] ksum ,int[] nums,int av){
    if (i>=nums.length) {
        for (int j=0;j<k;j++){
            if (ksum[j]!=av){
                return false;
            }
        }  
        return true;
    }  
    int nexti = i+1;
    for(int j=0;j<k;j++){
        if (ksum[j]+nums[i]<=av){
            ksum[j] = ksum[j]+nums[i];
            if (dfs(nexti,k,ksum,nums,av)){
                return true;
            }
            ksum[j] = ksum[j]-nums[i];
        }
    }
    return false; 
}

}
‘’’