Untitled

vector<vector<int>> memo;
vector<int> arr;

int dp(int w, int n){
    if (w == 0) return 0;
    if (n == 0) return 1e8;

    int &ans = memo[w][n];
    if (ans != -1) return ans;
    
    ans = 1e8;
    if (arr[n] > w) ans = dp(w, n-1);
    else{
        int include = 1 + dp(w - arr[n], n-1);
        int exclude = dp(w, n-1);
        ans = min(include, exclude);
    }
    return ans;
}


int Solution::solve(const vector<int> &A) {
    int n = A.size();
        
    if (n == 1) return 0;
    if (n == 2){
        if (A[0]*A[1] > 0) return 1;
        else return 0;
    }
    
    vector<int> sortedA = A;
    sort(sortedA.begin(), sortedA.end());
    
    int total = 0;
    for (int x: sortedA) total += x;

    int capacity = total/2;    
    memo.assign(capacity+1, vector<int>(n+1, -1));
    arr = A;
    
    return dp(capacity, n-1);
    
}