Partition to K equal sum subsets

Posted: 7 Nov, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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.
Approach 1
  • 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.
Try Problem