Partition to K equal sum subsets

Moderate
0/80
Average time to solve is 40m
profile
Contributed by
38 upvotes
Asked in companies
Goldman SachsMicrosoftMyntra

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
1
8
4 3 1 3 4 3 1 2 
3
Sample Input 2:
True
Explanation for sample input 1:
It's possible to divide it into 3 subsets (4, 3), (1, 3, 3), (4, 2, 1) with equal sum = 7.
Sample Input 2:
1
7
5 1 2 6 7 1 2
4
Sample Output 2:
False
Hint

Try all possible combinations of ‘K’ subsets.

Approaches (2)
Exhaustive Search, DFS, BackTracking.
  • 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.
Time Complexity

O(K * (2 ^ N ), where ‘N’ is the number of elements in the input array and ‘K’ the number of subsets in which the array is to be divided.

 

As we are traversing the entire array for each subset. So for each subset, we are choosing the suitable elements from the array (basically iterate over the array and for each element either use it or drop it, which is O(2 ^ N). We are doing the same for each subset. Total subsets are ‘K’. So the overall Time Complexity will be O(K * (2 ^ N)).

Space Complexity

O(N), where ‘N’ is the number of elements in the input array.

 

As, we are traversing the entire array for each subset, the height of the recursion tree would still remain O(N) as we are not calling the recursive function for already visited elements. Also, O(N) for the visited array. So the Space Complexity becomes stack size + VISITED array = O(N)+O(N) = O(N).

Code Solution
(100% EXP penalty)
Partition to K equal sum subsets
Full screen
Console