<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>

class Solution:
  def __init__(self):
    self.kMaxNum = 16

  def minimumIncompatibility(self, nums: list[int], k: int) -> int:
    kMaxCompatibility = (16 - 1) * (16 // 2)
    n = len(nums)
    subsetSize = n // k
    maxMask = 1 << n
    incompatibilities = self._getIncompatibilities(nums, subsetSize)

    # dp[i] := the minimum possible sum of incompatibilities of the subset
    # of numbers represented by the bitmask i
    dp = [kMaxCompatibility] * maxMask
    dp[0] = 0

    for mask in range(1, maxMask):
      # The number of 1s in `mask` isn't a multiple of `subsetSize`.
      if mask.bit_count() % subsetSize != 0:
        continue
      # https://cp-algorithms.com/algebra/all-submasks.html
      submask = mask
      while submask > 0:
        if incompatibilities[submask] != -1:  # valid submask
          dp[mask] = min(dp[mask], dp[mask - submask] +
                         incompatibilities[submask])
        submask = (submask - 1) & mask

    return dp[-1] if dp[-1] != kMaxCompatibility else -1

  def _getIncompatibilities(
      self,
      nums: list[int],
      subsetSize: int,
  ) -> list[int]:
    """
    Returns an incompatibilities array where
    * incompatibilities[i] := the incompatibility of the subset of numbers
      represented by the bitmask i
    * incompatibilities[i] := -1 if the number of 1s in the bitmask i is not
      `subsetSize`
    """
    maxMask = 1 << len(nums)
    incompatibilities = [-1] * maxMask
    for mask in range(maxMask):
      if mask.bit_count() == subsetSize and self._isUnique(nums, mask, subsetSize):
        incompatibilities[mask] = self._getIncompatibility(nums, mask)
    return incompatibilities

  def _isUnique(self, nums: list[int], mask: int, subsetSize: int) -> bool:
    """Returns True if the numbers selected by `mask` are unique."""
    used = 0
    for i, num in enumerate(nums):
      if mask >> i & 1:
        used |= 1 << num
    return used.bit_count() == subsetSize

  def _getIncompatibility(self, nums: list[int], mask: int) -> int:
    """
    Returns the incompatibility of the selected numbers represented by the
    `mask`.
    """
    mn = self.kMaxNum
    mx = 0
    for i, num in enumerate(nums):
      if mask >> i & 1:
        mx = max(mx, num)
        mn = min(mn, num)
    return mx - mn
17500