 # About the Equal Average Partition : Solved category

#1

(Replace this first paragraph with a brief description of your new category. This guidance will appear in the category selection area, so try to keep it below 200 characters. Until you edit this description or create topics, this category won’t appear on the categories page.)

Use the following paragraphs for a longer description, or to establish category guidelines or rules:

• Why should people use this category? What is it for?

• How exactly is this different than the other categories we already have?

• What should topics in this category generally contain?

• Do we need this category? Can we merge with another category, or subcategory?

#2

//Bottom up DP approach
vector<vector > Solution::avgset(vector &A) {

``````int n=A.size();
int sum=0;
for(int i=0;i<n;i++)
sum+=A[i];
sort(A.begin(),A.end());
bool dp[sum+1][n+1];
memset(dp,false,sizeof(dp));
dp=true;
int curr1=n+2;
int curr2=-1;
for(int j=0;j<n;j++){
for(int k=n;k>=1;k--){
for(int i=sum;i>=0;i--){
if(i-A[j]>=0 and dp[i-A[j]][k-1]!=false)
{
dp[i][k]=true;
if(k*sum==i*n and k<=curr1){
//cout<<i<<" "<<k<<endl;
curr1=k;
curr2=i;
}
}
}
}
}
``````

vector<vector> ans;
if(curr1>=n)
return ans;
multiset s;
for(int i=0;i<n;i++)
s.insert(A[i]);

``````vector<int> v2;
vector<int> v1;
while(curr2!=0){
auto it=s.begin();

if(curr2-(*it)>=0 and dp[curr2-(*it)][curr1-1]==true)
{   curr2=curr2-(*it);
//cout<<*it<<endl;
v1.push_back(*it);
s.erase(it);
curr1--;
}
else
{   //cout<<*it<<endl;
v2.push_back(*it);
s.erase(it);
}
}
``````

while(s.size()>0){
v2.push_back(*s.begin());
s.erase(s.begin());
}
ans.push_back(v1);
ans.push_back(v2);
return ans;
}