Very intutive video solution


#1

I found a very good video of this solution.


#2

vector<vector > Solution::avgset(vector &A) {
//Bottom up DP approach (Knapsack)
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[0][0]=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(ksum==in 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;
}