1681. Minimum Incompatibility

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 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 <= 16
• nums.length is divisible by k
• 1 <= nums[i] <= nums.length

Problem Summary

Given an integer array nums and an integer k. You need to divide this array into k subsets of the same size, such that there are no two equal elements in the same subset. The incompatibility of a subset is the difference between the maximum and minimum values in that subset.

Return the minimum value of the sum of the incompatibilities of each subset after dividing the array into k subsets. If it is impossible to divide it into k subsets, return -1. A subset is defined as a collection of some numbers in the array, with no requirement on the order of the numbers.

Solution Approach

• The most straightforward idea after reading the problem is DFS. The approach is similar to problem 77, so it will not be elaborated here. You can refer to the solution for problem 77.
• This problem also requires a greedy idea. Each time we choose a number, choose the smallest number. This can avoid putting the maximum and minimum numbers in the same set. Since each number chosen each time is the smallest, it can ensure that the incompatibility is minimized as much as possible each time. Therefore, define the order of choosing numbers in the order array. Then sort the array in ascending order. In this way, whenever numbers are chosen according to the order sequence, the chosen number is the smallest value.
• A normal DFS solution takes a long time after submission, about 1532ms. How can it be optimized to the extreme? Here, 2 pruning conditions need to be added. The first pruning condition is relatively simple: if the accumulated sum is greater than the previously stored res, return directly and do not continue recursion. The second pruning condition is very important and can greatly reduce the number of recursive calls. Whenever choosing numbers to form a new set, start from the first smallest number; once it is chosen, there is no need to continue looping recursively afterward. For example, for [1,2,3,4], if the first number chosen is 2, the sets can be [[2,3],[1,4]] or [[2,4], [1,3]], which are the same cases as [[1,3],[2,4]] and [[1,4], [2,3]]. It can be seen that after taking the first smallest value, the subsequent loop is unnecessary. Therefore, when choosing the number at index 0, after the recursion reaches the bottom and returns, we can directly break, without continuing the subsequent loop; the subsequent loop and recursion are unnecessary. We do not care about the order within each group, as long as the maximum and minimum values are within the group. Also, we do not care about the order between groups. Therefore, the permutation problem with O(n!) time complexity can be reduced to a combination problem with O(2^n). After adding these 2 pruning conditions, the runtime becomes 0ms. beats 100%

Code

package leetcode

import (
	"math"
	"sort"
)

func minimumIncompatibility(nums []int, k int) int {
	sort.Ints(nums)
	eachSize, counts := len(nums)/k, make([]int, len(nums)+1)
	for i := range nums {
		counts[nums[i]]++
		if counts[nums[i]] > k {
			return -1
		}
	}
	orders := []int{}
	for i := range counts {
		orders = append(orders, i)
	}
	sort.Ints(orders)
	res := math.MaxInt32
	generatePermutation1681(nums, counts, orders, 0, 0, eachSize, &res, []int{})
	if res == math.MaxInt32 {
		return -1
	}
	return res
}

func generatePermutation1681(nums, counts, order []int, index, sum, eachSize int, res *int, current []int) {
	if len(current) > 0 && len(current)%eachSize == 0 {
		sum += current[len(current)-1] - current[len(current)-eachSize]
		index = 0
	}
	if sum >= *res {
		return
	}
	if len(current) == len(nums) {
		if sum < *res {
			*res = sum
		}
		return
	}
	for i := index; i < len(counts); i++ {
		if counts[order[i]] == 0 {
			continue
		}
		counts[order[i]]--
		current = append(current, order[i])
		generatePermutation1681(nums, counts, order, i+1, sum, eachSize, res, current)
		current = current[:len(current)-1]
		counts[order[i]]++
		// This is the key pruning
		if index == 0 {
			break
		}
	}
}