# Partition of Array [duplicate]

Given an integer array. You have to check whether it is possible to divide the array in two parts such that the sum of elements of one part is equal to the sum of the element of the other part.If it is possible print "YES" otherwise "NO".

Sample Input

4 3 5 5 3


Sample Output

YES


Explanation

Array can be divided in two parts {4,3,3} and {5,5}


Sample Input

1 3


Sample Output

NO


Sample Input

5 5


Sample Output

YES

• This looks like it simplifies to the subset sum problem. Feb 6, 2014 at 13:51
• Do you accept True/False as output? Feb 6, 2014 at 15:11
• @PeterTaylor That asked people to find if the sum of a group in the array equals 0. This asks people if the sum of one group is the same as the sum of another group within the same array. The techniques used are very similar, but the outcome is completely different.
– user10766
Feb 6, 2014 at 19:03
• @user2509848, applying the standard rule of thumb for duplicates (how much effort is required to port a solution from the older question?), I think the answer here is "not enough". All that is required is a trivial change to the input (add -sum(input)/2 to the input array) and a trivial change to the output. Feb 6, 2014 at 19:07
• OK, I guess it is a duplicate. I was thinking of a completely different approach.
– user10766
Feb 6, 2014 at 19:18

# Ruby 98

f=->a{s=a.inject :+;(1..a.count).any?{|i|a.combination(i).any?{|r|r.inject(:+)*2==s}}?'Yes':'No'}

• Why not (1..a.size) ? Apr 4, 2016 at 18:42

# Prolog

Without proper output (92 chars)

s(A):-s(A,0,0).
s([],B,B).
s([H|T],B,C):-D is B+H,s(T,D,C).
s([H|T],B,C):-D is C+H,s(T,B,D).


With proper output (121 chars)

s(A):-(s(A,0,0),print('YES'),!;print('NO')).
s([],B,B).
s([H|T],B,C):-D is B+H,s(T,D,C).
s([H|T],B,C):-D is C+H,s(T,B,D).


To query the rules:

s([4,3,5,5,3])
s([1,3])


# Ruby with ActiveSupport 74

p (1..a.size).any?{|b|a.combination(b).any?{|c|c.sum*2==a.sum}}?'YES':'NO'


# Ruby 88

p (1..a.size).any?{|b|a.combination(b).any?{|c|c.reduce(:+)*2==a.reduce(:+)}}?'YES':'NO'


# Mathematica 59

f@a_ := If[Select[Subsets@a, Tr@# == Tr@a/2 &] == {}, "NO\n", "YES\n"]


The Logic

If there exists no subset of the input integer array, a, having, as its total, one-half of the total of a, then NO. Else, YES.

Examples

f[{4, 3, 5, 5, 3}]


YES

f[{4, 3, 5}]


NO

• It prints YES and NO for the same example?
– user10766
Feb 6, 2014 at 16:20
• No. I mis-entered the second input! Feb 6, 2014 at 16:56

# Haskell - 113 (30 chars for imports)

import Control.Monad(filterM)
f x|t="YES"
|1>0="NO"where t=or$map(==(sum x)/2)$map(sum)$filterM(\_->[0>1,1>0])x  Query by calling f on a list: *Main> f [4,3,5,5,3] "YES" *Main> f [1,3] "NO" *Main> f [5,5] "YES"  This is my first attempt at golfing in Haskell, if anyone has any tips for shortening my code they are welcomed. ## MATLAB 75 64 Quite happy with this. Too bad the function names are so much characters. @(x)['NO '+[11,-10,51]*ismember(sum(x)/2,cumsum(perms(x),2)) '']  # Javascript Only works in browsers with ECMAScript 6 support (Firefox works). Defines a function that can be called with a list of integers, the target sum value, and the length of the list. ## 53 characters (sans formatting and specific criteria) q=(l,s,i)=>--i>=0&&(q(l,s,i)||l[i]==s||q(l,s-l[i],i))  This will work with both positive and negative floating point numbers as well, not just integers. It can also find whether the list at any point can sum to any arbitrary sum, which is much more general than the problem requires. ## 106 Characters (with formatting and starting criteria) q=(l,i,s)=>--i>=0&&(q(l,i,s)||l[i]==s||q(l,i,s-l[i]));f=l=>q(l,l.length,l.reduce((a,b)=>a+b)/2)?'YES':'NO'  Fully half of the code here is just boilerplate required to limit the solution to this specific case, and format the output according to the criteria. A non recursive solution that builds the table from the bottom is more efficient but also takes more characters. ## GolfScript 64 47 ~:x[[]]{{+}+1$%+}@/(;{{+}*2*x{+}*=},'YES''NO'if


Explanation: Find a subset (using this subset method) whose sum is exactly half of the total sum of the input.

Previous solution:

~].,.))2?,{2base}%\{\,=}+,\{]zip{~\2*(*}%}+%{{+}*!},'YES''NO'if


Explanation: This uses base to count and find every possible array of length n comprised of only 1s and 0s. Then it uses this array to negate or do nothing to elements of the initial array. For example, for input [1 2 3], we would have [1 2 3][1 2 -3][1 -2 3][1 -2 -3][-1 2 3][-1 2 -3][-1 -2 3][-1 -2 -3]. The program then returns 'YES' if and only if the sum of the elements of any of these arrays is 0. Negating some subset of the array, then adding all the elements and checking if it equals 0 is clearly equivalent to checking for a 2-part partition.

I'm sure this implementation can be improved upon, but I think the idea is there.

~]1,\{2*{1$+}+%}/)2/?)!"YES NO"n/=  The code basically calculates the totals of all possible subsets and then searches for (half of) the overall total in this list. (Actualy the code calculates doubles all the subset sums and searches for the list's total in order to not conflict with integer division.) You can see the example running online. > 4 3 5 5 3 YES > 4 5 5 5 3 NO  ## C#, 169 bytes It enumerates through a series of arrays of the same length as the input. Each array contains a list of +1 and -1 values which are multiplied against each corresponding input value. If the sum of the multiplied arrays is zero, then some numbers sum to the same as the rest of the numbers. For the sake of golfing the +1/-1 array is actually +2/0 and 1 subtracted from it when used. Example: input = n = { 4, 3, 5, 5, 3 } polarity = p = { +1, +1, -1, -1, +1 } n*p = { +4, +3, -5, -5, +3 } result = x = Sum(n*p) == 0  Code: bool S(int[]n){ int i=0,l=n.Length,s; var x=false; var p=new int[l+1]; while(i>=0){ s=0; for(i=l;i-->0;) s+=n[i]*(p[i]-1); x|=s==0; for(i=l;p[i]<1&&i-->0;) p[i]=2-p[i]; } return x; }  Test: Console.WriteLine(S(new[]{4,3,5,5,3})); True Console.WriteLine(S(new[]{1,3})); False Console.WriteLine(S(new[]{2})); False Console.WriteLine(S(new[]{0})); True // Presuming Sum{0} == Sum{}  # C++ — 294 275 Not very compact, but you don't often see C++ in code challenges! ### Features • can get NO result in O(1) time for many inputs • uses no external algorithms for generating subsets, all in code • C++ was used for easy vector creation ### Code #include <iostream> #include <vector> using namespace std;int main(){vector<int>v;int s,e,w,g,t;for(s=0;cin>>e;s+=e)v.push_back(e);if(!(s&1)){s/=2;w=v.size();for(e=0;e<1<<w;e++){for(g=0,t=0;g<w;g++)if(e&1<<g)t+=v[g];if(t==s){cout<<"YES\n";return 0;}}}cout<<"NO\n";return 1;}  ### To compile g++ -o partition partition.cpp  ### Examples $ echo 4 3 5 5 3 | ./partition
YES

$echo {1..28} | ./partition YES # after a slight delay$ echo 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 29 | ./partition
NO # after a long delay

\$ echo {1..29} | ./partition
NO # immediately


### Limitations

• upper limit is 29 elements, could use unsigned long long int` to extend to 61 or 62 elements, but the basic idea is the same