UVA 10664 – Luggage Solution

#include<bits/stdc++.h>


using namespace std;
int dp[205][25];
bool isSubArray(int a[], int sum,int n)
{
    if(sum==0){
        return true;
    }
    if(n<0){
        return false;
    }
    if(a[n]>sum){
        return dp[sum][n]=isSubArray(a,sum,n-1);
    }
    if(dp[sum][n]==-1)
        return dp[sum][n]=(isSubArray(a,sum,n-1)||isSubArray(a,sum-a[n],n-1));
    else return dp[sum][n];
}


int main()
{
    int test;
    scanf("%d",&test);
    getchar();
    int a[25];
    while(test--)
    {
        string str;
        getline(cin,str);
        stringstream st;
        st<<str;
        int i=0,s=0,n;
        while(st>>n){
            a[i++]=n;
            s+=n;
        }
        memset(dp,-1,sizeof(dp));
        if(s%2==1) cout<<"NO"<<endl;
        else{
            if(isSubArray(a,s/2,i-1)){
                cout<<"YES"<<endl;
            }
            else{
                cout<<"NO"<<endl;
            }
        }
    }

    return 0;
}