最小不兼容性

/*
题目思路：
1. 计算nums的长度，如果不能被k整除，直接返回-1。
2. 使用回溯法尝试将数组划分为k个子集。
3. 确保每个子集中没有重复元素。
4. 计算每个子集的最大值和最小值的差，并累加得到不兼容性和。
5. 返回最小的不兼容性和。
*/
import java.util.*;
import java.util.stream.IntStream;

public class Solution {
    public int minimumIncompatibility(int[] nums, int k) {
        int n = nums.length;
        if (n % k != 0) return -1;
        int subsetSize = n / k;
        Arrays.sort(nums);
        int[] dp = new int[1 << n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        IntStream.range(0, 1 << n).forEach(mask -> {
            if (Integer.bitCount(mask) % subsetSize == 0) {
                IntStream.range(0, n).filter(i -> (mask & (1 << i)) == 0).forEach(i -> {
                    int nextMask = mask | (1 << i);
                    int minVal = nums[i], maxVal = nums[i];
                    for (int j = i + 1; j < n; j++) {
                        if ((mask & (1 << j)) == 0 && nums[j] != nums[i]) {
                            nextMask |= (1 << j);
                            maxVal = nums[j];
                        }
                    }
                    dp[nextMask] = Math.min(dp[nextMask], dp[mask] + maxVal - minVal);
                });
            }
        });
        return dp[(1 << n) - 1] == Integer.MAX_VALUE ? -1 : dp[(1 << n) - 1];
    }
}