You are given an integer array nums​​​ and an integer k. You are asked to distribute this array into k subsets of equal size such that there are no two equal elements in the same subset.

A subset's incompatibility is the difference between the maximum and minimum elements in that array.

Return the minimum possible sum of incompatibilities of the k subsets after distributing the array optimally, or return -1 if it is not possible.

A subset is a group integers that appear in the array with no particular order.

&nbsp;
Example 1:

Input: nums = [1,2,1,4], k = 2
Output: 4
Explanation: The optimal distribution of subsets is [1,2] and [1,4].
The incompatibility is (2-1) + (4-1) = 4.
Note that [1,1] and [2,4] would result in a smaller sum, but the first subset contains 2 equal elements.

Example 2:

Input: nums = [6,3,8,1,3,1,2,2], k = 4
Output: 6
Explanation: The optimal distribution of subsets is [1,2], [2,3], [6,8], and [1,3].
The incompatibility is (2-1) + (3-2) + (8-6) + (3-1) = 6.


Example 3:

Input: nums = [5,3,3,6,3,3], k = 3
Output: -1
Explanation: It is impossible to distribute nums into 3 subsets where no two elements are equal in the same subset.


&nbsp;
Constraints:


	1 &lt;= k &lt;= nums.length &lt;= 16
	nums.length is divisible by k
	1 &lt;= nums[i] &lt;= nums.length


class Solution(object):
    def minimumIncompatibility(self, nums, k):
        nums.sort(reverse = True)
        upperbound = len(nums) // k
        arr = [[] for _ in range(k)]
        self.res = float('inf')
        def assign(i):
            if i == len(nums):
                self.res = min(self.res, sum(arr[i][0]-arr[i][-1] for i in range(k)))
                return True
            flag = 0
            for j in range(k):
                if not arr[j] or (len(arr[j]) < upperbound and arr[j][-1] != nums[i]):
                    arr[j].append(nums[i])
                    if assign(i+1):
                        flag += 1
                    arr[j].pop()
                if flag >= 2: break
            return flag != 0
        if max(collections.Counter(nums).values()) > k: return -1
        assign(0)
        return self.res
class Solution {
    public int minimumIncompatibility(int[] nums, int k) {
        Arrays.sort(nums);
        k=nums.length/k;
        int n = nums.length,INF=100;
        int[][] dp = new int[1<<n][n];
        for (int[] d : dp){
            Arrays.fill(d, INF);
        }
        for (int i=0;i<n;i++){
            dp[1<<i][i]=0;
        }
        for (int i = 1; i < 1<<n; i++){
            int c = Integer.bitCount(i);
            for (int j=0;j<n&&c%k==0;j++){
                for (int w=0;w<n&&(i&1<<j)>0;w++){
                    if ((i&1<<w)==0){
                        dp[i|1<<w][w]=Math.min(dp[i|1<<w][w], dp[i][j]);
                    }
                }
            }
            for (int j=0;j<n&&c%k!=0;j++){
                for (int w=j+1;w<n&&(i&1<<j)>0;w++){
                    if ((i&1<<w)==0&&nums[w]!=nums[j]){
                        dp[i|1<<w][w]=Math.min(dp[i|1<<w][w], dp[i][j]+nums[w]-nums[j]);
                    }
                }
            }
        }
        int ans = Arrays.stream(dp[(1<<n)-1]).min().getAsInt();
        return ans==INF?-1:ans;
    }
}
const int INF = 1e9;

class Solution {
public:
    int minimumIncompatibility(vector<int>& nums, int k) {
        int i, n = nums.size(), subset_size = n / k;
        sort(nums.begin(), nums.end());

        // Pre-calculate the range (max - min) for each subset of nums
        // Note that there are (1 << n) subsets (i.e. 2 ^ n subsets) of an array of size n
        vector<int> range(1 << n, INF);

        // Each mask represents every possible subset of elements in num (so, "mask" == "subset")
        // Specifically, if the bit at position i of mask is set to 1, then we include that number in the subset
        for(int mask = 1; mask < (1 << n); mask++) {
            int small = -1, big = -1;
            bool dup = false;

            // Identify elements that belong to this subset, find the largest & smallest, check for duplicates
            // Recall that this array was sorted in the beginning of the function
            for(i=0; i<n && !dup; i++)
                if(mask & (1 << i)) {
                    if(small == -1)
                        small = nums[i];
                    if(big == nums[i])
                        dup = true;
                    big = nums[i];
                }

            // If no duplicates were found, then calculate and store the range for this subset
            if(!dup)
                range[mask] = big - small;
        }

        vector<int> dp(1 << n, INF);
        dp[0] = 0;

        // Iterate over every mask (i.e. subset) and calculate its minimum sum
        for(int mask = 1; mask < (1 << n); mask++) {

            // Iterate over every submask for current mask
            for(int submask = mask; submask; submask = (submask - 1) & mask) {

                // Check that submask has the right number of elements
                if(__builtin_popcount(submask) == subset_size)
                    // Note that mask = submask + (mask ^ submask)
                    // ==> i.e., mask ^ submask = mask - submask
                    // In other words, (mask ^ submask) represents those elements in mask that are not in submask
                    dp[mask] = min(dp[mask], range[submask] + dp[mask ^ submask]);
            }
        }
        // dp.back() == dp[(1 << n) - 1];
        return dp.back() >= INF ? -1 : dp.back();
    }
};
////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////


var minimumIncompatibility = function(nums, k) {
	////// FROM HERE TO
    if (nums.length === k) return 0;
    
    const maxInBucket = nums.length / k;
    const freqCount = {};
    for (const n of nums) {
        if (freqCount[n]) {
            if (freqCount[n] === k) {
                return -1
            } else {
                freqCount[n]++
            }
        } else {
            freqCount[n] = 1
        }
    }
	/////// HERE is just saving time
    
	// create a cache (aka memo, dp, dynamic programming, momoization)
    const cache = {}
	// create a mask to know when all the indicies are used
    const allIndiciesUsedMask = 2 ** nums.length - 1;
    
    const dfs = (usedIndicesBitMask) => {
	    // if we have used all the indicies then we return 0
        if (usedIndicesBitMask === allIndiciesUsedMask) {
            return 0;
        }
		// if we have seen this combination before, return the
		// result that was calculated before
		// otherwise do the hard work LOL
        if (cache[usedIndicesBitMask]) {
            return cache[usedIndicesBitMask];
        }
        
		// find all the indicies that are available to be used
		// skip duplicate values
        const valsToIndices = {};
        for (let i = 0; i < nums.length; i++) {
            const indexMask = 1 << i;
            if (usedIndicesBitMask & indexMask) continue;
            const value = nums[i];
            if (!valsToIndices.hasOwnProperty(value)) {
                valsToIndices[value] = i;
            }
        }
        const indicesAvailable = Object.values(valsToIndices);

        // this is hard to explain but it's basically calculating the minimum
		// cost while marking the indicies that are going to be used for each
		// combination
        let minIncompatibilityCost = Infinity;
        const combinations = createCombinations(indicesAvailable, maxInBucket);
        for (const indices of combinations) {
            let nextMask = usedIndicesBitMask;
            let minVal = Infinity;
            let maxVal = -Infinity;
            for (const index of indices) {
                minVal = Math.min(minVal, nums[index]);
                maxVal = Math.max(maxVal, nums[index]);
                nextMask = nextMask | (1 << index);
            }
            const incompatibilityCost = maxVal - minVal;
            minIncompatibilityCost = 
                Math.min(minIncompatibilityCost, dfs(nextMask) + incompatibilityCost);
        }
        return cache[usedIndicesBitMask] = minIncompatibilityCost;
    }
    return dfs(0);
};

function createCombinations(indices, len) {
    const combinations = [];
    
    if (indices.length < len) {
        return combinations;
    }
    
    const stack = [[[], 0]];
    while (stack.length > 0) {
        let [combi, i] = stack.pop();
        for (; i < indices.length; i++) {
            const combination = [...combi, indices[i]];
            if (combination.length === len) {
                combinations.push(combination);
            } else {
                stack.push([combination, i + 1]);
            }
        }
    }
    
    return combinations;
}
Minimum Incompatibility