Last Updated: 7 Nov, 2020
Partition to K equal sum subsets
Moderate
Asked in companies
You are given an array of 'N' integers, and a positive integer 'K'. You need to determine if it is possible to divide the array into 'K' non-empty subsets such that the sum of elements of each subset is equal.
Note:
1. The array can have duplicate elements.
2. Each of the array elements must belong to exactly one of the 'K' subsets.
3. The elements chosen for a subset may not be contiguous in the array.
Input Format:
The first line of the input contains an integer 'T', denoting the number of test cases.
The first line of each test case will contain an integer 'N', denoting the size of the input array.
The second line of each test case will contain 'N' space-separated integers denoting the array elements.
The third and last line of each input will contain the value 'K', which denotes the number of non-empty subsets you have to break the input array into.
Output Format:
For each test case, print a single line containing “True” if it is possible to divide the array into ‘K' equal sum subsets, “False” otherwise.
The output of each test case will be printed in a separate line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 15
0 <= NUMS[i] <= 10 ^ 3
1 <= K <= N
Where NUMS[i] denotes ith element of given array 'NUMS'.
Time Limit: 1 sec.
Approaches
- The underlying problem is to divide the input array into K subsets so that all the subsets have equal sums.
- So, if the sum of all the elements of the input array is not divisible by K, that is remainder != 0, then the given array can not be divided into K equal sum subsets. So, return false. Also if the largest element of the array is greater than (sum of elements of the array) / K, then return false.
- So what we are going to do is use backtracking( or we can say depth-first search) to find k subsets with each sum = SUM / K, where SUM is the sum of elements of the array.
- To keep track of which of the elements are already included in some subset, we will maintain a VISITED array such that VISITED[i] = true, if the ith element is already included in some subset, and false otherwise.
- Now we will start filling elements in subsets by trying each unvisited element as a possible candidate for this subset. We will also maintain a count to store how many valid subsets are found till now. As soon as we form a valid subset we increase the count.
- For every subset, we will try to fill all the elements so that their sum reaches SUM / K (where SUM is the total sum of the array), and we can move to fill the next subset.
- For every unvisited element, we have two options: take it or ignore it. We can only take the element if the current sum of the subset + element is not greater than the required sum for each subset. When we try the ‘ith’ element as a possible candidate for the current subset then we recursively look for more elements from (i +1)th index onwards.
- If we successfully find K subsets then we return true, else return false.
- The underlying problem is to divide the input array into 'K' subsets so that all the subsets have equal sums.
- So, if the sum of all the elements of the input array is not divisible by 'K', that is remainder != 0, then the given array can not be divided into 'K' equal sum subsets. So, return false.
- Else, it may/may not be possible. Why? Because we have to add complete elements to a subset, and it is not guaranteed that the sum would be perfectly equal to sum/'K', where sum = sum of all elements of array arr[]. Here we will call sum / K, EACHSUM.
- Since, given N = 15 (at max.), we can use bitmasks to store the sums of subsets. For e.g. for N = 15, we want to group them into 'K' subsets, but there are (1<<15) possible subsets which represent all possible groups of elements.
- Here in a mask, if ith bit is set in the mask is set to 1 that means we have included that element in some of the subset. Else, we have not included that element yet in any of our subset.
- Obviously, we have to include an element into our subsets just once.
- So, we make a DP[1<<N] size auxiliary array and initialize it to - 1, denoting that state has not been reached yet.
- DP[i] means after reaching mask = i, the sum of all numbers in the array (marked as 1 in the binary representation of mask = i) modulo EACHSUM.
- We need to assure that, after reaching mask = (1<<N) - 1, from all possible paths, in at least one of the paths our DP[(1<<N) - 1] = 0. Which will mean all the sum was successfully distributed into 'K' non-empty subsets. If it is so, return True.
- If after going through all the transitions, we didn't get DP[(1<<N) - 1] == 0, that means, all the elements cannot be distributed into 'K' subsets so that sum of all the elements of each subset is equal to EACHSUM.
Similar problems