 New update is available. Click here to update.

# Minimum Costs Of Subsets

Last Updated: 12 Apr, 2021
Difficulty: Hard

## PROBLEM STATEMENT

#### You are given an array ARR of ‘N’ Integers and an integer. Your task is to divide this array into ‘K’ subsets satisfying the following constraints-

``````1. Each element in ARR belongs to exactly one subset.
2. All the elements in a subset are unique.
3. Each subset has a size of ‘N’/ ’K’
``````

#### For example :

``````[1,2,3,1,2,5] k=2
[[1,2,3],[1,2,5]] is a valid subset division. All the elements in each subset are unique and the the cost of construction is (3 - 1) + (5 - 1) = 6
``````
##### Input Format :
``````The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.

The first line and the only line of each test case contain two single space-separated integers, ‘N’ and ‘K’.

The second line of each test case contains N space-separated integers representing the elements of the array ARR.
``````
##### Output Format :
``````For each test case print the minimum cost of construction.
Output for each test case is printed in a separate line.
``````
##### Note :
``````You don’t need to print anything. It has already been taken care of. Just implement the given function.
``````
##### Constraints :
``````1 <= T <= 5
1 <= N <= 12
1 <= K <= N
1<= ARR[i] <= 20
K is a devisor of the N

Time Limit: 1 sec
`````` ## Approach 1

The answer depends on the smallest and the largest element in the subset. We will iterate over all the submasks of the array and the last element taken in this mask. Number the set bits in the mask will give the idea about if we are starting a new subset or ending a current subset. We will create a subset from the smallest element to the largest element.

groupSize = size of each group/subset

If we are starting a new group with i’th element then this element will be the smallest element in our new group so we will subtract it

If we are ending a group with i’th element then this will be the largest element in our group so we will add it

If we are adding the i’th element and it is not starting or ending a group than

The algorithm will be :

1. Calulate number of element in each subset (let groupSize= n/k)
2. dp[(1<<n)][ n ]

dp[mask][last] represents the minimum cost to group all the elements in the mask and the last element taken is ‘last’

1. For i in range(n)
1. dp[1<<i][ i ] = - arr[i]

Base case here we are starting a new subset having only i’th element

1. SETBITS = number of set bits in mask
2. For CURRENT  in range(n)
1. For NEXT in range(n)