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

<p>A subset&#39;s <strong>incompatibility</strong> is the difference between the maximum and minimum elements in that array.</p>

<p>Return <em>the <strong>minimum possible sum of incompatibilities</strong> of the </em><code>k</code> <em>subsets after distributing the array optimally, or return </em><code>-1</code><em> if it is not possible.</em></p>

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

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,1,4], k = 2
<strong>Output:</strong> 4
<strong>Explanation:</strong> 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.</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [6,3,8,1,3,1,2,2], k = 4
<strong>Output:</strong> 6
<strong>Explanation:</strong> 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.
</pre>

<p><strong class="example">Example 3:</strong></p>

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= k &lt;= nums.length &lt;= 16</code></li>
	<li><code>nums.length</code> is divisible by <code>k</code></li>
	<li><code>1 &lt;= nums[i] &lt;= nums.length</code></li>
</ul>

from collections import Counter
from itertools import combinations
from functools import lru_cache

def print_used(used):
    i = 0
    ans = []
    while used:
        if used & (1 << i):
            ans.append(i)
        used = used & (used - 1)
        i += 1
    return ans


class Solution:
    def minimumIncompatibility(self, nums: List[int], k: int) -> int:

        @lru_cache(None)
        def next(used, size):
            n = len(nums)
            current_nums = [nums[i] for i in range(n) if not (used & (1 << i))]
            if not current_nums:
                return 0
            unique = set(current_nums)
            min_cost = float("inf")
            for selected in combinations(unique, size):
                # Update used mask.
                current_used = used
                for s in selected:                    
                    for i, e in enumerate(nums):
                        if s == e and not (current_used & (1 << i)):
                            current_used |= (1<<i)
                            break
                    # print(s, current_used)
                
                # print(f"{selected=} {print_used(current_used)=}")
                cost = max(selected) - min(selected)
                if cost >= min_cost:
                    continue
                child_cost = next(current_used, size)
                
                min_cost = min(min_cost, cost + child_cost)
            return min_cost
        
        # print(f"{nums=}")
        if len(nums) % k != 0:            
            return -1

        if len(nums) == k:
            return 0

        count = Counter(nums)
        size = len(nums) // k
        for num, c in count.items():
            if c > k:
                # print(f"{num=}, {k=} {c=} {size=}")
                return -1

        
        min_cost = next(0, size)
        if min_cost == float("inf"):
            return -1
        return min_cost


24900