划分k个相等子集

输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
输出： True
说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和

桶问题：若可以划分为k个子集，则想象有k个桶，容量均为sum/k，如果我们刚好将桶装满，则返回true，否则返回false

class Solution {
    int sum =0;
    public boolean canPartitionKSubsets(int[] nums, int k) {
        if(!isValid(nums,k)) return false;
        //对数组排序，从后向前搜索
        Arrays.sort(nums);
        if(nums[nums.length-1]>sum/k) return false;
        sum/=k;
        int[] arr = new int[k];
        //建立桶的数据结构
        Arrays.fill(arr,sum);
        return(backTrack(nums,k,arr,nums.length-1));
    }
    boolean isValid(int[] nums, int k){
        for(int val : nums) sum+=val;
        if(sum%k!=0) return false;
        return true;
    }
    boolean backTrack(int[] nums, int k,int[] arr,int cur){
        if(cur<0) return true;// cur走到-1时，说明所有的数全部都放进桶里了。这时一定是true
        for(int i=0;i<k;i++){
            //i遍历每一个桶，判断cur指向的数可以放入哪一个桶
            if(arr[i]==nums[cur]||arr[i]-nums[cur]>=nums[0]){
                arr[i]-=nums[cur];
                if(backTrack(nums,k,arr,cur-1)) return true;
                arr[i]+=nums[cur];
            }
        }
        return false;
    }
}