划分为k个相等的子集

/*
题目思路：
1. 计算数组的总和并检查是否能被k整除。
2. 使用目标和计算每个子集的目标和。
3. 使用Stream对数组排序并进行反转。
4. 通过递归函数尝试将每个数字分配到k个子集中。
5. 使用辅助数组来跟踪每个子集的当前和。
*/
 
import java.util.Arrays;
import java.util.Collections;
import java.util.stream.Collectors;
 
public class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = Arrays.stream(nums).sum();
        if (sum % k != 0) return false;
        int target = sum / k;
        nums = Arrays.stream(nums).boxed().sorted(Collections.reverseOrder()).mapToInt(Integer::intValue).toArray();
        int[] bucket = new int[k];
        return canPartition(nums, bucket, target, 0);
    }
 
    private boolean canPartition(int[] nums, int[] bucket, int target, int index) {
        if (index == nums.length) return true;
        for (int i = 0; i < bucket.length; i++) {
            if (bucket[i] + nums[index] > target) continue;
            bucket[i] += nums[index];
            if (canPartition(nums, bucket, target, index + 1)) return true;
            bucket[i] -= nums[index];
            if (bucket[i] == 0) break;
        }
        return false;
    }
}