LeetCode 698 划分为k个相等的子集

698. 划分为k个相等的子集

给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。

示例 1：

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

注意:

1 <= k <= len(nums) <= 16
0 < nums[i] < 10000

思路：首先判断不可能的条件：
1.当数组中的数不能等分为K个非空子集 也就是数组中各元素和取余K不为0时，不可能
2.如果可以均分还要判断数组中最大的那个数是否大于各元素和取余K的值 如果大于很明显也不能均分
判断完毕后就要通过递归函数来开始划分K个相等的子集
思路就是建立长度为K的桶，每个桶中事先放入均分计算得到的元素值，然后每次向桶中放入新的元素时减去新元素的值，并判断相减之后的值是否大于数组由小到大排序后的第一个值也就是最小值，如果大于就说明可以继续放下一个数。再通过该递归函数判断下一个数可不可以放到该桶中（有可能由于下一个数过大而无法放入，那么这时就得向前挪移一个单元试试比他小的数可不可以放入桶中） 就这样依次递归下去 直到这个桶完全放满为止。 然后再放下一个桶，直到所有的元素都放入了桶中，就说明可以把这个数组分成K个非空子集，其总和都相等。
源代码如下：

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        //因为题目限制条件不用担心溢出
        int sum = 0;
        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
        }
        if(sum % k != 0){
            return false;
        }
        //求出子集的和
        sum = sum / k;
        //排序 小的放最前面大的放最后面
        Arrays.sort(nums);
        //如果子集的和小于数组最大的直接返回false
        if(nums[nums.length - 1] > sum){
            return false;
        }
        //建立一个长度为k的桶
        int[] arr = new int[k];
        //桶的每一个值都是子集的和
        Arrays.fill(arr, sum);
        //从数组最后一个数开始进行递归
        return help(nums, nums.length - 1, arr, k);
    }

    boolean help(int[] nums, int cur, int[] arr, int k){
        //已经遍历到了-1说明前面的所有数都正好可以放入桶里，那所有桶的值此时都为0，说明找到了结果，返回true
        if(cur < 0){
            return true;
        }
        //遍历k个桶
        for(int i = 0; i < k; i++){
            //如果正好能放下当前的数或者放下当前的数后，还有机会继续放前面的数（剪枝）
            if(arr[i] == nums[cur] || (cur > 0 && arr[i] - nums[cur] >= nums[0])){
                //放当前的数到桶i里
                arr[i] -= nums[cur];
                //开始放下一个数
                if(help(nums, cur - 1, arr, k)){
                    return true;
                }
                //这个数不该放在桶i中
                //从桶中拿回当前的数
                arr[i] += nums[cur];
            }
        }
        return false;
    }
}