Subset Sum Problem!

• Time : $O(min(sum(A) - B, B) * n)$
• Space : $O(min(sum(A) - B, B))$

int Solution::solve(vector<int> &A, int B) {
    int sum = 0;
    for(auto a : A) sum += a;
    if(sum < B) return 0;
    B = min(B, sum - B);
    vector<int> dp(B + 1);
    dp[0] = 1;
    for(auto a : A) {
        for(int i = dp.size() - 1; i >= a; i--) {
            if(dp[i-a]) dp[i] = 1;
        }
    }
    
    return dp[B];
}