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 _theminimum possible sum of incompatibilities of the _ksubsets after distributing the array optimally, or return-1if it is not possible.
A subset is a group integers that appear in the array with no particular order.
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.
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.
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.
Since the array is small (n <= 16), we can use bitmask DP to try all possible ways to split the array into k groups of equal size, ensuring no duplicates in any group. For each valid group, we precompute its incompatibility and use DP to find the minimum sum.
defminimum_incompatibility(nums: list[int], k: int) -> int:
from itertools import combinations
n, m = len(nums), len(nums) // k
inf = float('inf')
inc = {}
for comb in combinations(range(n), m):
vals = [nums[i] for i in comb]
if len(set(vals)) < m: continue mask = sum(1<< i for i in comb)
inc[mask] = max(vals) - min(vals)
dp = [inf] * (1<< n)
dp[0] =0for mask in range(1<< n):
if dp[mask] == inf: continue unused = [i for i in range(n) ifnot (mask & (1<< i))]
if len(unused) < m: continuefor comb in combinations(unused, m):
submask = sum(1<< i for i in comb)
if submask in inc:
dp[mask | submask] = min(dp[mask | submask], dp[mask] + inc[submask])
return-1if dp[-1] == inf else dp[-1]
1
// Omitted for brevity, similar logic as C++
1
// Omitted for brevity, similar logic as JavaScript