Problem

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

Examples

Example 1

1
2
3
4
5
6
7
8

    
    
    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

1
2
3
4
5
6
7
8

    
    
    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

1
2
3
4
5
6
7

    
    
    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

Solution

Method 1 – Bitmask Dynamic Programming

Intuition

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.

Approach

  1. Calculate the size of each group: group_size = n // k.
  2. Precompute incompatibility for all valid subsets of size group_size (no duplicates).
  3. Use DP where dp[mask] is the minimum incompatibility for the subset of elements represented by mask.
  4. For each mask, try adding a valid group and update the DP value.
  5. If it’s impossible to split, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    int minimumIncompatibility(vector<int>& nums, int k) {
        int n = nums.size(), m = n / k;
        int inf = 1e9;
        vector<int> inc(1 << n, -1);
        for (int mask = 0; mask < (1 << n); ++mask) {
            if (__builtin_popcount(mask) != m) continue;
            set<int> s;
            int mx = 0, mn = 20;
            for (int i = 0; i < n; ++i) {
                if (mask & (1 << i)) {
                    if (s.count(nums[i])) { mx = -1; break; }
                    s.insert(nums[i]);
                    mx = max(mx, nums[i]);
                    mn = min(mn, nums[i]);
                }
            }
            if (mx != -1) inc[mask] = mx - mn;
        }
        vector<int> dp(1 << n, inf);
        dp[0] = 0;
        for (int mask = 0; mask < (1 << n); ++mask) {
            if (dp[mask] == inf) continue;
            vector<int> unused;
            for (int i = 0; i < n; ++i) if (!(mask & (1 << i))) unused.push_back(i);
            if (unused.size() < m) continue;
            int sub = 0;
            function<void(int,int,int)> gen = [&](int idx, int cnt, int cur) {
                if (cnt == m) {
                    if (inc[cur] != -1) dp[mask | cur] = min(dp[mask | cur], dp[mask] + inc[cur]);
                    return;
                }
                for (int j = idx; j < unused.size(); ++j) gen(j+1, cnt+1, cur | (1 << unused[j]));
            };
            gen(0,0,0);
        }
        return dp[(1<<n)-1] == inf ? -1 : dp[(1<<n)-1];
    }
};
1
// Omitted for brevity, similar logic as C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    public int minimumIncompatibility(int[] nums, int k) {
        int n = nums.length, m = n / k, inf = (int)1e9;
        int[] inc = new int[1 << n];
        Arrays.fill(inc, -1);
        for (int mask = 0; mask < (1 << n); mask++) {
            if (Integer.bitCount(mask) != m) continue;
            Set<Integer> s = new HashSet<>();
            int mx = 0, mn = 20;
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) > 0) {
                    if (s.contains(nums[i])) { mx = -1; break; }
                    s.add(nums[i]);
                    mx = Math.max(mx, nums[i]);
                    mn = Math.min(mn, nums[i]);
                }
            }
            if (mx != -1) inc[mask] = mx - mn;
        }
        int[] dp = new int[1 << n];
        Arrays.fill(dp, inf);
        dp[0] = 0;
        for (int mask = 0; mask < (1 << n); mask++) {
            if (dp[mask] == inf) continue;
            List<Integer> unused = new ArrayList<>();
            for (int i = 0; i < n; i++) if ((mask & (1 << i)) == 0) unused.add(i);
            if (unused.size() < m) continue;
            gen(unused, 0, 0, m, mask, dp, inc);
        }
        return dp[(1<<n)-1] == inf ? -1 : dp[(1<<n)-1];
    }
    private void gen(List<Integer> unused, int idx, int cnt, int cur, int mask, int[] dp, int[] inc) {
        int n = unused.size();
        int m = Integer.bitCount(cur);
        if (m == unused.size() / (unused.size() / cnt)) {
            if (inc[cur] != -1) dp[mask | cur] = Math.min(dp[mask | cur], dp[mask] + inc[cur]);
            return;
        }
        for (int j = idx; j < n; j++) gen(unused, j+1, cnt+1, cur | (1 << unused.get(j)), mask, dp, inc);
    }
}
1
// Omitted for brevity, similar logic as Java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
def minimum_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] = 0
    for mask in range(1 << n):
        if dp[mask] == inf: continue
        unused = [i for i in range(n) if not (mask & (1 << i))]
        if len(unused) < m: continue
        for 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 -1 if dp[-1] == inf else dp[-1]
1
// Omitted for brevity, similar logic as C++
1
// Omitted for brevity, similar logic as JavaScript

Complexity

  • ⏰ Time complexity: O(n^2 * 2^n), where n is the length of nums. We try all possible subsets and masks.
  • 🧺 Space complexity: O(2^n), for DP and incompatibility tables.