Easy dp + backtracking


#1

https://www.pastiebin.com/5d60ff969939c


#2

can you please comment your code for better understanding?


#3

vector<vector> average(vector a)
{
int total = 0;
for(int i = 0; i < a.size(); i++)
total += a[i];

vector<vector<int>> arr(total+1);
for(int i=0;i<=total;i++) arr[i].resize(a.size()+1,INT_MAX);
for(int i=0;i<=total;i++)
{
    for(int j=0;j<=a.size();j++)
    {
        if((j!=0 && j!=a.size()) && (i*(a.size()-j) ==(total-i)*j)) arr[i][j] = j;
    }
}
for(int k=a.size()-1;k>=0;k--)
{
    for(int i=0;i<=total;i++)
    {
        for(int j=0;j<=a.size();j++)
        {
            if((j!=0 && j!=a.size()) && (i*(a.size()-j) ==(total-i)*j)) arr[i][j] = j;
            if(j==a.size() || i+a[k]>total) continue;
            else arr[i][j] = min(arr[i+a[k]][j+1],arr[i][j]);
        }
    }
}
vector<vector<int>> ans;
if(arr[0][0]==INT_MAX) return ans;
int i = 0;
int j = 0;
int k = 0;
ans.resize(2);
while(1)
{
    if(k==a.size()) return ans;
    int op1 = arr[i+a[k]][j+1];
    int op2 = arr[i][j];
    if(op1<=op2) {ans[0].push_back(a[k]); i+=a[k]; j++; k++;}
    else {ans[1].push_back(a[k]); k++;}
}
return ans;

}

vector<vector > Solution::avgset(vector &A) {
sort(A.begin(), A.end());
return average(A);
}