An easy approach using dp


#1

int Solution::solve(const vector &A) {

int sum=0, n=A.size();
if(n<2) return 0;
for(int i=0;i<n;i++)
sum+=A[i];

sum=sum/2;
pair<bool,long long> dp[n+1][sum+1];
long long int ans=INT_MAX;
for(int i=0;i<=n;i++)
dp[i][0]={true,0};

for(int i=1;i<=sum;i++)
dp[0][i]={false,INT_MAX};

for(int i=1;i<=n;i++)
{
    for(int j=1;j<=sum;j++)
    {
        if(j>=A[i-1]) {
        dp[i][j].first=dp[i-1][j].first||dp[i-1][j-A[i-1]].first;
        if(dp[i][j].first==false)
            dp[i][j].second=INT_MAX;
        else
             dp[i][j].second=min(dp[i-1][j].second,1+dp[i-1][j-A[i-1]].second);
      
        }
        else dp[i][j]=dp[i-1][j];
    
    }
   
}

for(int i=sum;i>=1;i--)
{
    for(int j=1;j<=n;j++)
    {
        if(dp[j][i].first==true)
        {
            ans=min(ans,dp[j][i].second); f=1;
        }
    }
    if(f==1) break;
}

return ans;

}