Easy Solution DP+Backtracking


#1

vector<vector > Solution::avgset(vector &A) {
sort(A.begin(),A.end());
int n=A.size();
int s=0;
for(auto a:A){
s+=a;
}
vector<unordered_set > vec(n+1);
vec[0].insert(0);
for(auto a:A){
for(int i=n;i>=1;i–){
if(vec[i-1].size()!=0){
for(auto val:vec[i-1]){
vec[i].insert(a+val);
}
}
}
}
int len=-1,sum=-1;
for(int i=1;i<n;i++){
if(((is)%n)==0){
int l1=i,s1=(i
s)/n,l2=n-l1,s2=s-s1;
if(vec[i].find(s1)!=vec[i].end()){
int av1=s1/l1,av2=s2/l2;
//cout<<s1<<" “<<l1<<” “<<s2<<” “<<l2<<”\n";
if(av1==av2){
sum=s1;
len=l1;
break;
}
}
}
}
if(len==-1) return {};
vector an;
int l=len;
s=sum;
int i=0;
for(i=0;i<n;i++){
if(l==0){
break;
}
if(vec[l-1].find(s-A[i])!=vec[l-1].end()){
an.push_back(A[i]);
l–;
s-=A[i];
}
}
map<int,int> mp;
for(auto a:A){
mp[a]++;
}
for(auto t:an){
mp[t]–;
if(mp[t]==0){
mp.erase(t);
}
}
vector ret;
for(auto m:mp){
for(int i=0;i<m.second;i++){
ret.push_back(m.first);
}
}
sort(an.begin(),an.end());
sort(ret.begin(),ret.end());
return {an,ret};
}