SUBSET - Balanced Cow Subsets

Farmer John's owns N cows (2 <= N <= 20), where cow i produces M(i) units of milk each day (1 <= M(i) <= 100,000,000).

FJ wants to streamline the process of milking his cows every day, so he installs a brand new milking machine in his barn.

Unfortunately, the machine turns out to be far too sensitive: it only works properly if the cows on the left side of the barn have the exact same total milk output as the cows on the right side of the barn!

Let us call a subset of cows "balanced" if it can be partitioned into two groups having equal milk output.

Since only a balanced subset of cows can make the milking machine work, FJ wonders how many subsets of his N cows are balanced.

Please help him compute this quantity.

Input

  • Line 1: The integer N.
  • Lines 2..1+N: Line i+1 contains M(i).

Output

  • Line 1: The number of balanced subsets of cows.

Sample

Input
4
1
2
3
4

Output
3

Explanation

There are 4 cows, with milk outputs 1, 2, 3, and 4.

There are three balanced subsets: the subset {1,2,3}, which can be partitioned into {1,2} and {3}, the subset {1,3,4}, which can be partitioned into {1,3} and {4}, and the subset {1,2,3,4} which can be partitioned into {1,4} and {2,3}.


Added by:Ikhaduri
Date:2012-04-29
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Usaco open 2012

hide comments
2014-09-27 07:36:07 shahbaz khan
How can it solve since for generating subset 2^n time complexity is required and for check subset of a subset another 2^n time complexity please reply for less time complexity approach

Last edit: 2014-09-27 07:38:39
2014-03-17 10:36:59 himanshu kansal
can it be solved without generating all subsets??
2012-11-13 09:03:11 Ravi Kiran
Nice problem!
I would recommend trying case (before submit):
6
1 1 1 1 1 1
Ans = 31
2012-05-04 11:52:54 :D
Read the problem statement carefully. We are looking for a number of distict subsets that can be partitioned. We are NOT looking for number of different valid partitions.

For example solution to:
4
1 1 1 1

is: 7 not 9.

The description is correct in that regard. It's simply easy to mix up.
2012-05-03 12:44:49 :D
Please add like breaks. The lines are really long in some browsers (chrome, IE). Also see my comments for SUBSTATE problem.

RE: I can't see your comments for SUBSTATE problem, I think problem setter removed it.

RE RE: Yes, it's removed. Sorry, I was pretty sure it was your problem.

Also problem description still without proper line breaks. It may be due to the font, I don't know. I'm using chrome and this issue is practically never present for other problems.
RE: Fixed.

Last edit: 2012-05-03 12:45:31
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.