Minimum Incompatibility solution and explanation

def minIncompatibility(nums, k):
    from itertools import combinations
    nums.sort()
    n = len(nums)
    c = n // k
    if any(nums[i] == nums[i + c] for i in range(n - c)):
        return -1

    subsets = [set() for _ in range(k)]
    nums_used = [False] * n

    def backtrack(index):
        if index == n:
            return sum(max(s) - min(s) for s in subsets if s)

        for i in range(k):
            if len(subsets[i]) < c and (not subsets[i] or nums[index] not in subsets[i]):
                subsets[i].add(nums[index])
                nums_used[index] = True
                incompat = backtrack(index + 1)
                if incompat != -1:
                    return incompat
                subsets[i].remove(nums[index])
                nums_used[index] = False

            if not subsets[i]:
                break

        return -1

    return backtrack(0)

function minIncompatibility(nums, k) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const c = n / k;
    const subsets = Array.from({ length: k }, () => new Set());
    if (nums.some((num, i) => i + c < n && num === nums[i + c])) return -1;

    function backtrack(index) {
        if (index === nums.length) {
            return subsets.reduce((acc, set) => acc + (Math.max(...set) - Math.min(...set)), 0);
        }

        for (let i = 0; i < k; i++) {
            if (subsets[i].size < c && !subsets[i].has(nums[index])) {
                subsets[i].add(nums[index]);
                const incompat = backtrack(index + 1);
                if (incompat !== -1) return incompat;
                subsets[i].delete(nums[index]);
            }

            if (subsets[i].size === 0) break;
        }

        return -1;
    }

    return backtrack(0);
}

import java.util.Arrays;

public class Solution {
    public int minIncompatibility(int[] nums, int k) {
        int n = nums.length, c = n / k;
        Arrays.sort(nums);

        int[] dp = new int[1 << n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int mask = 0; mask < (1 << n); mask++) {
            int used = Integer.bitCount(mask);
            if (used % c != 0) continue;

            for (int i = 0; i < n; i++) {
                for (int j = i + 1; (j < n) && (j < i + c); j++) {
                    if ((mask & (1 << i)) == 0 && (mask & (1 << j)) == 0) {
                        int newMask = mask | (1 << i) | (1 << j);
                        dp[newMask] = Math.min(dp[newMask], dp[mask] + nums[j] - nums[i]);
                    }
                }
            }
        }

        return dp[(1 << n) - 1] == Integer.MAX_VALUE ? -1 : dp[(1 << n) - 1];
    }
}

#include <vector>
#include <algorithm>
#include <climits>
#include <unordered_map>
using namespace std;

int minIncompatibility(vector<int>& nums, int k) {
    int n = nums.size(), groupSize = n / k;
    sort(nums.begin(), nums.end());

    vector<int> dp(1 << n, INT_MAX);
    dp[0] = 0;

    for (int mask = 0; mask < (1 << n); ++mask) {
        int used = __builtin_popcount(mask);
        if (used % groupSize) continue;
        vector<int> availableIndices;
        for (int i = 0; i < n; ++i) {
            if (!(mask & (1 << i))) {
                availableIndices.push_back(i);
            }
        }

        for (int i = 0; i < availableIndices.size(); ++i) {
            for (int j = i + 1; j < availableIndices.size() && j < i + groupSize; ++j) {
                int submask = mask | (1 << availableIndices[i]) | (1 << availableIndices[j]);
                dp[submask] = min(dp[submask], dp[mask] + nums[availableIndices[j]] - nums[availableIndices[i]]);
            }
        }
    }

    return dp.back() == INT_MAX ? -1 : dp.back();
}

function minimumIncompatibility(nums: number[], k: number): number {
    const n = nums.length;
    const m = Math.floor(n / k);
    const g: number[] = Array(1 << n).fill(-1);
    for (let i = 1; i < 1 << n; ++i) {
        if (bitCount(i) !== m) {
            continue;
        }
        const s: Set<number> = new Set();
        let [mi, mx] = [20, 0];
        for (let j = 0; j < n; ++j) {
            if ((i >> j) & 1) {
                if (s.has(nums[j])) {
                    break;
                }
                s.add(nums[j]);
                mi = Math.min(mi, nums[j]);
                mx = Math.max(mx, nums[j]);
            }
        }
        if (s.size === m) {
            g[i] = mx - mi;
        }
    }
    const inf = 1e9;
    const f: number[] = Array(1 << n).fill(inf);
    f[0] = 0;
    for (let i = 0; i < 1 << n; ++i) {
        if (f[i] === inf) {
            continue;
        }
        const s: Set<number> = new Set();
        let mask = 0;
        for (let j = 0; j < n; ++j) {
            if (((i >> j) & 1) === 0 && !s.has(nums[j])) {
                s.add(nums[j]);
                mask |= 1 << j;
            }
        }
        if (s.size < m) {
            continue;
        }
        for (let j = mask; j; j = (j - 1) & mask) {
            if (g[j] !== -1) {
                f[i | j] = Math.min(f[i | j], f[i] + g[j]);
            }
        }
    }
    return f[(1 << n) - 1] === inf ? -1 : f[(1 << n) - 1];
}

function bitCount(i: number): number {
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}

public class Solution {
    public int MinimumIncompatibility(int[] nums, int k) {
        int n = nums.Length;
        int m = n / k;
        int[] g = new int[1 << n];
        Array.Fill(g, -1);
        for (int i = 1; i < 1 << n; ++i) {
            if (bitCount(i) != m) {
                continue;
            }
            HashSet<int> s = new();
            int mi = 20, mx = 0;
            for (int j = 0; j < n; ++j) {
                if ((i >> j & 1) == 1) {
                    if (s.Contains(nums[j])) {
                        break;
                    }
                    s.Add(nums[j]);
                    mi = Math.Min(mi, nums[j]);
                    mx = Math.Max(mx, nums[j]);
                }
            }
            if (s.Count == m) {
                g[i] = mx - mi;
            }
        }
        int[] f = new int[1 << n];
        int inf = 1 << 30;
        Array.Fill(f, inf);
        f[0] = 0;
        for (int i = 0; i < 1 << n; ++i) {
            if (f[i] == inf) {
                continue;
            }
            HashSet<int> s = new();
            int mask = 0;
            for (int j = 0; j < n; ++j) {
                if ((i >> j & 1) == 0 && !s.Contains(nums[j])) {
                    s.Add(nums[j]);
                    mask |= 1 << j;
                }
            }
            if (s.Count < m) {
                continue;
            }
            for (int j = mask; j > 0; j = (j - 1) & mask) {
                if (g[j] != -1) {
                    f[i | j] = Math.Min(f[i | j], f[i] + g[j]);
                }
            }
        }
        return f[(1 << n) - 1] == inf ? -1 : f[(1 << n) - 1];
    }

    private int bitCount(int x) {
        int cnt = 0;
        while (x > 0) {
            x &= x - 1;
            ++cnt;
        }
        return cnt;
    }
}

func minimumIncompatibility(nums []int, k int) int {
	n := len(nums)
	m := n / k
	const inf = 1 << 30
	f := make([]int, 1<<n)
	g := make([]int, 1<<n)
	for i := range g {
		f[i] = inf
		g[i] = -1
	}
	for i := 1; i < 1<<n; i++ {
		if bits.OnesCount(uint(i)) != m {
			continue
		}
		s := map[int]struct{}{}
		mi, mx := 20, 0
		for j, x := range nums {
			if i>>j&1 == 1 {
				if _, ok := s[x]; ok {
					break
				}
				s[x] = struct{}{}
				mi = min(mi, x)
				mx = max(mx, x)
			}
		}
		if len(s) == m {
			g[i] = mx - mi
		}
	}
	f[0] = 0
	for i := 0; i < 1<<n; i++ {
		if f[i] == inf {
			continue
		}
		s := map[int]struct{}{}
		mask := 0
		for j, x := range nums {
			if _, ok := s[x]; !ok && i>>j&1 == 0 {
				s[x] = struct{}{}
				mask |= 1 << j
			}
		}
		if len(s) < m {
			continue
		}
		for j := mask; j > 0; j = (j - 1) & mask {
			if g[j] != -1 {
				f[i|j] = min(f[i|j], f[i]+g[j])
			}
		}
	}
	if f[1<<n-1] == inf {
		return -1
	}
	return f[1<<n-1]
}