Easy DP solution in C++


#1

int Solution::solve(vector &A) {
int n=A.size();
int range=0;
for(int i=0;i<n;i++)
range += A[i];

bool dp[n+1][range+1];
int sum=range;

for(int i=0;i<=n;i++)
    dp[i][0]=true;
for(int j=1;j<=sum;j++)
    dp[0][j]=false;
for(int i=1;i<=n;i++){
    for(int j=1;j<=sum;j++){
        if(A[i-1]<=j)
            dp[i][j]=(dp[i-1][j] || dp[i-1][j-A[i-1]]);
        else
            dp[i][j]=dp[i-1][j];
    }
}

vector v;
for(int j=0;j<sum+1;j++)
{
if(dp[n][j]==true)
{
v.push_back(j);
}
}

int mn=INT_MAX;
for(int i=0;i<=v.size()/2;i++)
{
mn = min(mn,abs(range- 2*v[i]));
}
return mn;

}