# Partition to K Equal Sum Subsets

Given an array of integers **A[]** and a positive integer **k**, find whether it's possible to divide this array into **k** non-empty subsets whose sums are all equal.

The problem wants you to find if it is possible to partition given array into k subset such that each set has sum equal to (total sum of array/number of the required partition), keeping in mind that we can use one element in only one of the subset. If it is possible we are required to print "YES" otherwise "NO".

**Input:**

The first line of input consists of **T** number of test cases, following each test case, consist of **N** the size of the array following lined consist of **N** elements of the array.

**Output:**

You need to determine if it possible to divide the array into **K** subset of equal sum or not.

**Examples:**

Input:
T = 1
N = 5, K = 3
[2,1,4,5,6]
Output:
YES, as {1,5},{4,2} and {6}

Since we have the probability of either including the element into the subset or not including it which means we can choose some other element from the array for current element and place the other elements into some other subset, this implies the concept of backtracking.

So we will use the following steps:

kor notkthen simply return false otherwise proceed further, we will add each number of the arrayA[]into one ofkgroup as long as the sum of that group is not larger than the (sum/k) value.A[], if we are able to add all elements of theA[]then we returntrue, otherwise, we returnfalse.A[]array so that we first add the largest elements first.If our index reached <0 then it means that all elements of the given array have been used in some of the subset for partition and hence we return true.

Otherwise, we used current value and add it to vector and make a recursive call to check if leads to a solution or not, if not then we subtract that value and backtrack, if that index position in vector(use for partition) is still 0 then it means that partition is not possible and we return false.

Time Complexityfor the above approach is:O(k^(n-k)K!),nis array size andkis the required partition size.Space Complexityfor the above approach is :O(n)C++ Implementation:

need an explanation for this answer? contact us directly to get an explanation for this answerOutput: