Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

This question already has an answer here:

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
share|improve this question

marked as duplicate by Peter Taylor, Quincunx, hosch250, Cruncher, Paul R Feb 7 at 7:43

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

4  
This looks like it simplifies to the subset sum problem. –  Kendall Frey Feb 6 at 13:51
    
Do you accept True/False as output? –  David Carraher Feb 6 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. –  hosch250 Feb 6 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. –  Peter Taylor Feb 6 at 19:07
    
OK, I guess it is a duplicate. I was thinking of a completely different approach. –  hosch250 Feb 6 at 19:18

11 Answers 11

up vote 4 down vote accepted

Ruby 98

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

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])
share|improve this answer
    
+1 for Prolog. Thanks for memories. –  VisioN Feb 6 at 20:00

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'
share|improve this answer

Mathematica 59

With spaces for readability,

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

share|improve this answer
    
It prints YES and NO for the same example? –  hosch250 Feb 6 at 16:20
    
No. I mis-entered the second input! –  David Carraher Feb 6 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.

share|improve this answer

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)) '']
share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

GolfScript, 34 characters

~]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
share|improve this answer

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{}
share|improve this answer

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
share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.