UVA 10664 - Luggage

#include<bits/stdc++.h>
using namespace std;
long ar[110]= {0},tot=0,sum=0,dp[50][3000];
#define sf(a) scanf("%ld",&a)
long call(long i,long wt)
{
    if(i>tot)
        return 0;
    if(wt==sum/2)
        return 1;
    if(dp[i][wt]!=-1)
        return dp[i][wt];
    long ans=0;
    ans=ans|call(i+1,wt+ar[i]);
    ans=ans|call(i+1,wt);
    return dp[i][wt]=ans;
}
int main()
{
    long ts,num;
    string line;
    sf(ts);
    getchar();
    while(ts--)
    {
        getline(cin,line);
        stringstream ss;
        ss<<line;
        int cnt=0;
        sum=0;
        memset(dp,-1,sizeof(dp));
        while(ss>>num)
        {
            ar[cnt++]=num;
            sum+=num;
        }
        tot=cnt-1;

        if(sum%2==0)
        {
            // cout<<call(0,0);
            if(call(0,0))
                printf("YES\n");
            else
                printf("NO\n");
        }
        else
            printf("NO\n");
    }
    return 0;
}