1681. Minimum Incompatibility Hard

1/**
2 * [1681] Minimum Incompatibility
3 *
4 * 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.
5 * A subset's incompatibility is the difference between the maximum and minimum elements in that array.
6 * Return the minimum possible sum of incompatibilities of the k subsets after distributing the array optimally, or return -1 if it is not possible.
7 * A subset is a group integers that appear in the array with no particular order.
8 *  
9 * Example 1:
10 * 
11 * Input: nums = [1,2,1,4], k = 2
12 * Output: 4
13 * Explanation: The optimal distribution of subsets is [1,2] and [1,4].
14 * The incompatibility is (2-1) + (4-1) = 4.
15 * Note that [1,1] and [2,4] would result in a smaller sum, but the first subset contains 2 equal elements.
16 * Example 2:
17 * 
18 * Input: nums = [6,3,8,1,3,1,2,2], k = 4
19 * Output: 6
20 * Explanation: The optimal distribution of subsets is [1,2], [2,3], [6,8], and [1,3].
21 * The incompatibility is (2-1) + (3-2) + (8-6) + (3-1) = 6.
22 * 
23 * Example 3:
24 * 
25 * Input: nums = [5,3,3,6,3,3], k = 3
26 * Output: -1
27 * Explanation: It is impossible to distribute nums into 3 subsets where no two elements are equal in the same subset.
28 * 
29 *  
30 * Constraints:
31 * 
32 * 	1 <= k <= nums.length <= 16
33 * 	nums.length is divisible by k
34 * 	1 <= nums[i] <= nums.length
35 * 
36 */
37pub struct Solution {}
38
39// problem: https://leetcode.com/problems/minimum-incompatibility/
40// discuss: https://leetcode.com/problems/minimum-incompatibility/discuss/?currentPage=1&orderBy=most_votes&query=
41
42// submission codes start here
43
44impl Solution {
45    pub fn minimum_incompatibility(nums: Vec<i32>, k: i32) -> i32 {
46        0
47    }
48}
49
50// submission codes end
51
52#[cfg(test)]
53mod tests {
54    use super::*;
55
56    #[test]
57    fn test_1681() {
58    }
59}
60