Problem Link :https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1605

Solution Idea:

The main problem is an array of integers is given and we have to divide the array into two small array in such a way so that the sum of both arrays are same.

At first we take input and sum up the array values. if the total sum is odd then it’s confirm that we can’t split it into two equal sum. so that we can output “NO”.

If the sum is Even then we can use knapsack of Coin Change any algorithm to check if we can make the (sum/2) value from the given array values. Here I am using knapsack.

As the input of this problem is tricky because we don’t know how many numbers there will be in a line. So for this problem I use stringstream to solve this problem.

/*
         +-+ +-+ +-+
         |R| |.| |S|
         +-+ +-+ +-+
 */

#include <bits/stdc++.h>

#define pii             pair <int,int>
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout<<#x " = "<<(x)<<endl
#define VI              vector <int>
#define DBG             pf("Hi\n")
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf("%d",&a)
#define sfl(a)          scanf("%lld",&a)
#define sff(a,b)        scanf("%d %d",&a,&b)
#define sffl(a,b)       scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)     scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)    scanf("%lld %lld %lld",&a,&b,&c)
#define loop(i,n)       for(int i=0;i<n;i++)
#define REP(i,a,b)      for(int i=a;i<b;i++)
#define TEST_CASE(t)    for(int z=1;z<=t;z++)
#define PRINT_CASE      printf("Case %d: ",z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

vector<int> v;

int dp[30][110];

int knapsack(int idx, int val)
{
    if(val==0) return 1;
    if(idx==SZ(v)) return 0;

    int &ret=dp[idx][val];
    if(ret!=-1) return ret;

    int p=0,q=0;

    if(val-v[idx]>=0) p=knapsack(idx+1,val-v[idx]);
    q=knapsack(idx+1,val);

    return ret=p|q;

}

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);

    int m;
    cin>>m;
    getchar();
    while(m--)
    {
        string str;
        getline(cin,str);
        stringstream ss;
        ss<<str;
        int val;
        int sum=0;
        while(ss>>val)
        {
            v.pb(val);
            sum+=val;
        }

        if(sum & 1)
            cout<<"NO"<<endl;
        else
        {
            ms(dp,-1);
            if(knapsack(0,sum/2))
                cout<<"YES"<<endl;
            else
                cout<<"NO"<<endl;
        }

        v.clear();


    }

    return 0;
}