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 <= 16nums.lengthis divisible byk1 <= nums[i] <= nums.length
Related Topics:
Backtracking, Greedy
- Sort
Ain asending order - Handle special cases where
k = 1andk = N.
Let dp[mask][pre] be the minimum incompatibility we can get with:
mask: If theith bit is0, thenith number is used. Otherwise,ith number is available.pre: the index of the number selected in the previous choice.
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][0] = ... = dp[mask][N - 1] = min( dp[mask - (1 << p)][p] | 0 < p < N && (mask & (1 << p)) != 0 )
// OJ: https://leetcode.com/problems/minimum-incompatibility/
// Author: github.com/lzl124631x
// 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], 0, sizeof(dp[0]));
for (int mask = 1; mask < M; ++mask) {
if (__builtin_popcount(mask) % sz) {
for (int pre = 0; pre < N; ++pre) {
for (int p = pre + 1; p < N; ++p) {
if ((mask & (1 << p)) && A[p] > A[pre]) {
dp[mask][pre] = min(dp[mask][pre], dp[mask - (1 << p)][p] + A[p] - A[pre]);
}
}
}
} else {
for (int p = 0; p < N; ++p) {
if (mask & (1 << p)) dp[mask][0] = min(dp[mask][0], dp[mask - (1 << p)][p]);
}
for (int i = 1; i < N; ++i) dp[mask][i] = dp[mask][0];
}
}
return dp[M - 1][0] > 10000 ? -1 : dp[M - 1][0];
}
};