Partition to K equal sum subsets
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

Question

Partition to K equal sum subsets

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.

Accepted Answer

1. If K is 1, then we already have our answer, the complete array is only a subset with the same sum.
2. If N < K, then it is not possible to divide the array into subsets with an equal sum because we can’t divide the array into more than N parts.
3. If the sum of the array is not divisible by K, then it is not possible to divide the array. We will proceed only if k divides the sum. Our goal reduces to divide the array into K parts where the sum of each part should be array_sum/K

Accepted Answer

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.

Space Complexity: O(n)Explanation:

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).

Time Complexity: OtherExplanation:

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)).

Accepted Answer

Dynamic Programming, Bitmasks.

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<
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<
If after going through all the transitions, we didn't get DP[(1<

Space Complexity: O(2^n)Explanation:

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

As we are using an auxiliary DP array for all the masks. Therefore, overall space complexity will be O(2 ^ N).

Time Complexity: OtherExplanation:

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

As we are traversing the ‘MASK’ from 1 to 2 ^ N and for each mask we are iterating from 0 to (N - 1). So for each mask, we are checking the suitable conditions from the input array. So the overall Time Complexity will be O(N * (2 ^ N)).

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:

Input Format:

Output Format:

Note:

Constraints:

Top Nagarro SDE interview questions & answers

Popular interview questions of SDE