hardBacktrackingPure DSA~40 min
Distribute Items into Groups Minimizing Incompatibility
You split items with numeric attributes into k equal-size groups where no group may contain duplicate values. A group's incompatibility is its max minus its min. Minimize the total incompatibility.
Problem
Given an integer array nums of length n and an integer k that divides n, partition nums into k groups each of size n/k such that no group contains duplicate values. The incompatibility of a group is (max - min). Return the minimum possible sum of incompatibilities, or -1 if no valid partition exists.
Input
An integer array nums and an integer k.
Output
An integer: the minimum total incompatibility, or -1.
Constraints
- 1 <= n <= 16, k divides n
- 1 <= nums[i] <= n
Examples
Example 1
Input
nums = [1,2,1,4], k = 2
Output
4
Groups [1,2] and [1,4]: (2-1)+(4-1) = 1+3 = 4.
Example 2
Input
nums = [6,3,8,1,3,1,2,2], k = 4
Output
7
Four groups of size 2 give total incompatibility 7.