Cpp Solution | Similar to Subset Sum Difference


#1
int Solution::solve(const vector<int> &A) {
    int n = A.size();
    int sum = 0;
    for(int a : A) sum += a;
    sum/=2;
    vector<vector<int> > dp(n+1,vector<int>(sum+1,INT_MAX));
    for(int i = 0; i <= n; i++) {
        for(int j = 0; j <= sum; j++) {
            if(j == 0) dp[i][j] = 0;
            else if(i == 0) continue;
            else {
                dp[i][j] = dp[i-1][j];
                if(j >= A[i-1] && dp[i-1][j-A[i-1]] != INT_MAX) dp[i][j] = min(dp[i][j],1+dp[i-1][j-A[i-1]]);
            }
        }
    }
  
    while(sum >= 0) {
        if(dp[n][sum] != INT_MAX) return dp[n][sum];
        sum--;
    }
    return -1;
}