Techgig May contest : Partition problem : Level Easy

Problem Statement

You are given a set of positive integers. your task is to solve partition problem.

Lets define the partition problem.

Partition problem is the task of deciding whether a given multiset of positive integers can be partitioned into two subsets S1 and S2 such that the sum of the elements in S1 equals the sum of the elements in S2.

Example 1:
array[] = {1, 5, 11, 5}
Output: Yes
This array can be divided into to subsets {1, 5, 5} and {11} these two have equal sum.

Example 2: 
array[] = {1, 5, 3}
Output: No
This array cant be divided into two subsets of equal sum.

===============================================================================

The level set was easy but this was really a nice question, took half hour to code it.. :P

Well, Most of us get the answer just by reading the question... "Divide the array such that sum of each partition is equal", but as soon we we try to write the code, out mind keeps wondering "how the hell do I implement this ?"

I thought for some time and then realized that, The worst case of forming the partitions for N element is; One partition of 0 elements and the other of N elements, but this wont help us.

Now lets move forward in the same line. One partition of N-1 elements and the other of 1 element.This is our first step.

This can be easily achieved with a for loop. But, the problem is, there are many different ways for selection 2 partitions each of N-1 and 1 elements respectively. To be precise they are N ways.

First thing to be taken care of is to cover all the N ways. Next, every time the partition should be increase and decrease respectively keeping in mind all the cases.

Here is the code,

#include
#include

char* partition(int input1[])
{
           int i=0,n,total=0,loop,round,s1=0;
           while(input1[i]>-1)
           {
                if(input1[i]==0)return "Invalid";
                total+=input1[i++];
           }
           n=i;
           round=0;
           while(round < N)
           {
                loop=round;
                for(i=0;i<=round-1;i++)
                s1=s1+input1[i];
                while(loop < round)
               {
                   s1=s1+input1[loop];
                   if(s1==(total-s1))return "Yes";
                   s1=s1-input1[loop];
                   loop++;
               }
               s1=0;
               round++;
            }
            return "No";
}

Let me know if you have any doubts.

Continue