Formatted question description: https://leetcode.ca/all/1681.html

# 1681. Minimum Incompatibility (Hard)

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.

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.


Constraints:

• 1 <= k <= nums.length <= 16
• nums.length is divisible by k
• 1 <= nums[i] <= nums.length

Related Topics:
Backtracking, Greedy

### Preprocess

• Sort A in asending order
• Handle special cases where k = 1 and k = N.

### State Definition

Let dp[mask][pre] be the minimum incompatibility we can get with:

• mask: If the ith bit is 0, then ith number is used. Otherwise, ith number is available.
• pre: the index of the number selected in the previous choice.

### State Transition

We allocate the subsets one by one. For each subset, we allocate the numbers in ascending order.

We can use the number of 1 bits in mask, i.e. __builtin_popcount(mask), to know how many numbers are available.

If __builtin_popcount(mask) is not divisible by sz, then in the current choice we need to consider pre. To avoid duplicate numbers in the same subset, we must choose a number that is greater than A[pre]. Assume we chose A[p], then we added A[p] - A[pre] into the incompatibility.

          pre  p
v   v
A:       1 2 2 3 4 4 5 5 6
subset:  1 2   3

delta
incompa-   3 - 2 = 1
tibility


Transition formula:

dp[mask][pre] = min( dp[mask - (1 << p)][p] + A[p] - A[pre] | pre < p < N && A[p] > A[pre] && (mask & (1 << p)) != 0 )


If __builtin_popcount(mask) is divisible by sz, then we are allocating for a new subset. Now pre doesn’t matter. We just need to pick the first available number.

dp[mask] = ... = dp[mask][N - 1] = min( dp[mask - (1 << p)][p] | 0 < p < N && (mask & (1 << p)) != 0 )

// OJ: https://leetcode.com/problems/minimum-incompatibility/

// Time: O(2^N * N^2)
// Space: O(2^N * N)
// Ref: https://leetcode-cn.com/problems/minimum-incompatibility/solution/lao-tao-lu-zhuang-tai-ya-suo-dp-by-newha-j58b/
class Solution {
public:
int minimumIncompatibility(vector<int>& A, int k) {
int N = A.size(), M = 1 << N, sz = N / k;
if (k == 1) {
set<int> s(begin(A), end(A));
return s.size() == A.size() ? *s.rbegin() - *s.begin() : -1;
}
if (k == N) return 0;
sort(begin(A), end(A));
int dp[M][N];
memset(dp, 0x3f, sizeof(dp)); // infinity
memset(dp, 0, sizeof(dp));
for (int pre = 0; pre < N; ++pre) {
for (int p = pre + 1; p < N; ++p) {
if ((mask & (1 << p)) && A[p] > A[pre]) {
}
}
}
} else {
for (int p = 0; p < N; ++p) {
}
for (int i = 1; i < N; ++i) dp[mask][i] = dp[mask];
}
}
return dp[M - 1] > 10000 ? -1 : dp[M - 1];
}
};


Java

class Solution {
public int minimumIncompatibility(int[] nums, int k) {
int length = nums.length;
int[] value = new int[1 << length];
Arrays.fill(value, -1);
int[] freq = new int[length + 1];
for (int i = 0; i < 1 << length; i++) {
if (Integer.bitCount(i) == length / k) {
for (int j = 0; j < length; j++) {
if ((i & (1 << j)) != 0)
freq[nums[j]]++;
}
boolean flag = true;
for (int j = 1; j <= length; j++) {
if (freq[j] > 1) {
flag = false;
break;
}
}
if (flag) {
int low = Integer.MAX_VALUE, high = Integer.MIN_VALUE;
for (int j = 1; j <= length; ++j) {
if (freq[j] > 0) {
low = Math.min(low, j);
high = Math.max(high, j);
}
}
value[i] = high - low;
}
for (int j = 0; j < length; ++j) {
if ((i & (1 << j)) != 0) {
--freq[nums[j]];
}
}
}
}
int[] dp = new int[1 << length];
Arrays.fill(dp, -1);
dp = 0;
for (int i = 1; i < 1 << length; i++) {
if (Integer.bitCount(i) % (length / k) == 0) {
for (int j = i; j != 0; j = (j - 1) & i) {
if (value[j] != -1 && dp[i ^ j] != -1) {
if (dp[i] == -1)
dp[i] = dp[i ^ j] + value[j];
else
dp[i] = Math.min(dp[i], dp[i ^ j] + value[j]);
}
}
}
}
return dp[(1 << length) - 1];
}
}