Equal Subset Partitioning

You are given an array of integers and a positive integer k. Your task is to determine whether the array can be partitioned into k non-empty subsets such that the sum of the elements in each subset is equal.

Let \(S\) be the total sum of the array. For a valid partition, it must hold that \(S \mod k = 0\). In this case, each subset must sum to \(T = \frac{S}{k}\). Otherwise, such a partitioning is impossible. Use an appropriate backtracking approach to decide if the partition exists.

inputFormat

The first line of input contains a single integer T representing the number of test cases. For each test case, the first line contains two integers N and k, where N is the number of array elements. The second line contains N space-separated integers representing the array elements.

outputFormat

For each test case, print a single line containing either YES if it is possible to partition the array into k subsets with equal sum, or NO if it is not possible.

3
4 2
4 3 2 3
5 3
3 3 3 4 2
6 4
2 5 1 6 2 4

YES
NO
NO