#include <stdio.h> //Code taken and modified from www.geeksforgeeks.org/backttracking-set-4-subset-sum/
#include <stdlib.h>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
static int total_nodes;
int k,flag=0,x=0,y=0;
vector <int> v;
int c=0;
int a=0,n;
bool checkDuplicates(vector<int> array, int n)
{ //To be coded yet..to make disjoint subsets
}
// prints subset found
void printSubset(int A[], int size)
{
for(int i = 0; i < size; i++)
{
v.push_back(A[i]);
a++; //Number of elements
cout<<A[i]<<" ";
}
cout<<"\n";
c++; //Number of subsets
if(c==k)
{
if(!checkDuplicates(v,a)) //If duplicates are not found then set flag = 1
{
if(a==n)
{
flag=1;
}
else
flag=0;
}
}
}
//
// qsort compare function
int comparator(const void *pLhs, const void *pRhs)
{
int *lhs = (int *)pLhs;
int *rhs = (int *)pRhs;
return *lhs > *rhs;
}
// inputs
// s - set vector
// t - tuplet vector
// s_size - set size
// t_size - tuplet size so far
// sum - sum so far
// ite - nodes c
// target_sum - sum to be found
void subset_sum(int s[], int t[],
int s_size, int t_size,
int sum, int ite,
int const target_sum)
{
total_nodes++;
if( target_sum == sum )
{
// We found sum
printSubset(t, t_size);
// constraint check
if( ite + 1 < s_size && sum - s[ite] + s[ite+1] <= target_sum )
{
// Exclude previous added item and consider next candidate
subset_sum(s, t, s_size, t_size-1, sum - s[ite], ite + 1, target_sum);
}
return;
}
else
{
// constraint check
if( ite < s_size && sum + s[ite] <= target_sum )
{
// generate nodes along the breadth
for( int i = ite; i < s_size; i++ )
{
t[t_size] = s[i];
if( sum + s[i] <= target_sum )
{
// consider next level node (along depth)
subset_sum(s, t, s_size, t_size + 1, sum + s[i], i + 1, target_sum);
}
}
}
}
//cout<<"INVOKED\n";
}
// Wrapper that prints subsets that sum to target_sum
void generateSubsets(int s[], int size, int target_sum)
{
int *tuplet_vector = (int *)malloc(size * sizeof(int));
int total = 0;
// sort the set
qsort(s, size, sizeof(int), &comparator);
for( int i = 0; i < size; i++ )
{
total += s[i];
}
if( s[0] <= target_sum && total >= target_sum )
{
subset_sum(s, tuplet_vector, size, 0, 0, 0, target_sum);
}
free(tuplet_vector);
}
int main()
{
int T;
int weights[1000];
scanf("%d",&T);
while(T)
{
flag=0;
long long sum=0;
int i=0,w=0;
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)
{
scanf("%d",&weights[i]);
sum+=weights[i];
if(weights[i]==0)
w++;
}
if(w==n)
{
printf("yes\n");
break;
}
int size = n;
if(sum%k!=0)
{
printf("no\n");
break;
}
//checkDuplicates1(weights,n);
int target = sum/k;
generateSubsets(weights,n,target);
v.clear();
if(flag==1 && a==n)
printf("yes\n");
else
printf("no\n");
//printf("Nodes generated %d\n", total_nodes);
T--;
}
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+IC8vQ29kZSB0YWtlbiBhbmQgbW9kaWZpZWQgZnJvbSB3d3cuZ2Vla3Nmb3JnZWVrcy5vcmcvYmFja3R0cmFja2luZy1zZXQtNC1zdWJzZXQtc3VtLyAKI2luY2x1ZGUgPHN0ZGxpYi5oPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8aW9zdHJlYW0+CiNpbmNsdWRlIDxhbGdvcml0aG0+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnN0YXRpYyBpbnQgdG90YWxfbm9kZXM7CmludCBrLGZsYWc9MCx4PTAseT0wOwp2ZWN0b3IgPGludD4gdjsKaW50IGM9MDsKaW50IGE9MCxuOwpib29sIGNoZWNrRHVwbGljYXRlcyh2ZWN0b3I8aW50PiBhcnJheSwgaW50IG4pCnsgLy9UbyBiZSBjb2RlZCB5ZXQuLnRvIG1ha2UgZGlzam9pbnQgc3Vic2V0cwoKfQovLyBwcmludHMgc3Vic2V0IGZvdW5kCnZvaWQgcHJpbnRTdWJzZXQoaW50IEFbXSwgaW50IHNpemUpCnsKCiAgICBmb3IoaW50IGkgPSAwOyBpIDwgc2l6ZTsgaSsrKQogICAgewogICAgICAgICB2LnB1c2hfYmFjayhBW2ldKTsKICAgICBhKys7IC8vTnVtYmVyIG9mIGVsZW1lbnRzCiAgICAgY291dDw8QVtpXTw8IiAiOwogICAgIH0KICAgIGNvdXQ8PCJcbiI7CiAgICBjKys7IC8vTnVtYmVyIG9mIHN1YnNldHMKICAJaWYoYz09aykKIAl7CglpZighY2hlY2tEdXBsaWNhdGVzKHYsYSkpIC8vSWYgZHVwbGljYXRlcyBhcmUgbm90IGZvdW5kIHRoZW4gc2V0IGZsYWcgPSAxCgl7CgkJaWYoYT09bikKCQl7CgkJCWZsYWc9MTsKCQl9CgkJZWxzZSAKCQlmbGFnPTA7CgkgfQoJfQogfQogLy8JIAovLyBxc29ydCBjb21wYXJlIGZ1bmN0aW9uCmludCBjb21wYXJhdG9yKGNvbnN0IHZvaWQgKnBMaHMsIGNvbnN0IHZvaWQgKnBSaHMpCnsKICAgIGludCAqbGhzID0gKGludCAqKXBMaHM7CiAgICBpbnQgKnJocyA9IChpbnQgKilwUmhzOwogCiAgICByZXR1cm4gKmxocyA+ICpyaHM7Cn0KIAovLyBpbnB1dHMKLy8gcyAgICAgICAgICAgIC0gc2V0IHZlY3RvcgovLyB0ICAgICAgICAgICAgLSB0dXBsZXQgdmVjdG9yCi8vIHNfc2l6ZSAgICAgICAtIHNldCBzaXplCi8vIHRfc2l6ZSAgICAgICAtIHR1cGxldCBzaXplIHNvIGZhcgovLyBzdW0gICAgICAgICAgLSBzdW0gc28gZmFyCi8vIGl0ZSAgICAgICAgICAtIG5vZGVzICBjCi8vIHRhcmdldF9zdW0gICAtIHN1bSB0byBiZSBmb3VuZAp2b2lkIHN1YnNldF9zdW0oaW50IHNbXSwgaW50IHRbXSwKICAgICAgICAgICAgICAgIGludCBzX3NpemUsIGludCB0X3NpemUsCiAgICAgICAgICAgICAgICBpbnQgc3VtLCBpbnQgaXRlLAogICAgICAgICAgICAgICAgaW50IGNvbnN0IHRhcmdldF9zdW0pCnsKICAgIHRvdGFsX25vZGVzKys7CiAgICBpZiggdGFyZ2V0X3N1bSA9PSBzdW0gKQogICAgewogICAgICAgIC8vIFdlIGZvdW5kIHN1bQogICAgICAgIHByaW50U3Vic2V0KHQsIHRfc2l6ZSk7CiAgICAgICAgLy8gY29uc3RyYWludCBjaGVjawogICAgICAgICAgaWYoIGl0ZSArIDEgPCBzX3NpemUgJiYgc3VtIC0gc1tpdGVdICsgc1tpdGUrMV0gPD0gdGFyZ2V0X3N1bSApCiAgICAgICAgewogICAgICAgICAgICAvLyBFeGNsdWRlIHByZXZpb3VzIGFkZGVkIGl0ZW0gYW5kIGNvbnNpZGVyIG5leHQgY2FuZGlkYXRlCiAgICAgICAgICAgIHN1YnNldF9zdW0ocywgdCwgc19zaXplLCB0X3NpemUtMSwgc3VtIC0gc1tpdGVdLCBpdGUgKyAxLCB0YXJnZXRfc3VtKTsKICAgICAgICB9CiAgICAgICAgcmV0dXJuOwogICAgfQogICAgZWxzZQogICAgewogICAgICAgIC8vIGNvbnN0cmFpbnQgY2hlY2sKICAgICAgICBpZiggaXRlIDwgc19zaXplICYmIHN1bSArIHNbaXRlXSA8PSB0YXJnZXRfc3VtICkKICAgICAgICB7CiAgICAgICAgICAgIC8vIGdlbmVyYXRlIG5vZGVzIGFsb25nIHRoZSBicmVhZHRoCiAgICAgICAgICAgIGZvciggaW50IGkgPSBpdGU7IGkgPCBzX3NpemU7IGkrKyApCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHRbdF9zaXplXSA9IHNbaV07CiAKICAgICAgICAgICAgICAgIGlmKCBzdW0gKyBzW2ldIDw9IHRhcmdldF9zdW0gKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIC8vIGNvbnNpZGVyIG5leHQgbGV2ZWwgbm9kZSAoYWxvbmcgZGVwdGgpCiAgICAgICAgICAgICAgICAgICAgc3Vic2V0X3N1bShzLCB0LCBzX3NpemUsIHRfc2l6ZSArIDEsIHN1bSArIHNbaV0sIGkgKyAxLCB0YXJnZXRfc3VtKTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KICAKCSAgLy9jb3V0PDwiSU5WT0tFRFxuIjsKfQogCi8vIFdyYXBwZXIgdGhhdCBwcmludHMgc3Vic2V0cyB0aGF0IHN1bSB0byB0YXJnZXRfc3VtCnZvaWQgZ2VuZXJhdGVTdWJzZXRzKGludCBzW10sIGludCBzaXplLCBpbnQgdGFyZ2V0X3N1bSkKewogICAgaW50ICp0dXBsZXRfdmVjdG9yID0gKGludCAqKW1hbGxvYyhzaXplICogc2l6ZW9mKGludCkpOwogCiAgICBpbnQgdG90YWwgPSAwOwogCiAgICAvLyBzb3J0IHRoZSBzZXQKICAgIHFzb3J0KHMsIHNpemUsIHNpemVvZihpbnQpLCAmY29tcGFyYXRvcik7CiAKICAgIGZvciggaW50IGkgPSAwOyBpIDwgc2l6ZTsgaSsrICkKICAgIHsKICAgICAgICB0b3RhbCArPSBzW2ldOwogICAgfQogCiAgICBpZiggc1swXSA8PSB0YXJnZXRfc3VtICYmIHRvdGFsID49IHRhcmdldF9zdW0gKQogICAgewogCiAgICAgICAgc3Vic2V0X3N1bShzLCB0dXBsZXRfdmVjdG9yLCBzaXplLCAwLCAwLCAwLCB0YXJnZXRfc3VtKTsKIAogICAgfQogICAgZnJlZSh0dXBsZXRfdmVjdG9yKTsKfQogCmludCBtYWluKCkKewoJaW50IFQ7CglpbnQgd2VpZ2h0c1sxMDAwXTsKCXNjYW5mKCIlZCIsJlQpOwoJd2hpbGUoVCkKCXsKCQlmbGFnPTA7CgkJbG9uZyBsb25nIHN1bT0wOwoJCWludCBpPTAsdz0wOwoJCXNjYW5mKCIlZCVkIiwmbiwmayk7CgkJZm9yKGludCBpPTA7aTxuO2krKykKCQl7CgkJc2NhbmYoIiVkIiwmd2VpZ2h0c1tpXSk7CgkJc3VtKz13ZWlnaHRzW2ldOwoJCWlmKHdlaWdodHNbaV09PTApCgkJdysrOwoJCX0KCQlpZih3PT1uKQoJCXsKCQlwcmludGYoInllc1xuIik7CgkJYnJlYWs7CgkJfQogICAgCWludCBzaXplID0gbjsKICAgIAlpZihzdW0layE9MCkKICAgIAl7CiAgICAJcHJpbnRmKCJub1xuIik7CiAgICAJYnJlYWs7CiAgICAJfQogICAgICAgLy9jaGVja0R1cGxpY2F0ZXMxKHdlaWdodHMsbik7CiAgICAgICBpbnQgdGFyZ2V0ID0gc3VtL2s7CgkgICBnZW5lcmF0ZVN1YnNldHMod2VpZ2h0cyxuLHRhcmdldCk7CiAgICAgICB2LmNsZWFyKCk7CglpZihmbGFnPT0xICYmIGE9PW4pCglwcmludGYoInllc1xuIik7CgllbHNlCglwcmludGYoIm5vXG4iKTsKICAgIC8vcHJpbnRmKCJOb2RlcyBnZW5lcmF0ZWQgJWRcbiIsIHRvdGFsX25vZGVzKTsKICAgIFQtLTsKCX0KICAgIHJldHVybiAwOwp9