Partition of Array [duplicate]

Question

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

Answer 1

Ruby 98

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

Answer 2

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])

Answer 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'

Answer 4

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

Answer 5

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.

Answer 6

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)) '']

Answer 7

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.

Answer 8

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.

Answer 9

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

Answer 10

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{}

Answer 11

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