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 FORMAT:
* Line 1: The integer N.
* Lines 2..1+N: Line i+1 contains M(i).
SAMPLE INPUT
4
1
2
3
4
INPUT DETAILS:
There are 4 cows, with milk outputs 1, 2, 3, and 4.
OUTPUT FORMAT:
* Line 1: The number of balanced subsets of cows.
SAMPLE OUTPUT:
3
OUTPUT DETAILS:
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}.
hide comments
shahbaz khan:
20140927 07:36:07
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: 20140927 07:38:39 

himanshu kansal:
20140317 10:36:59
can it be solved without generating all subsets?? 

Ravi Kiran:
20121113 09:03:11
Nice problem!


:D:
20120504 11:52:54
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.


:D:
20120503 12:44:49
Please add like breaks. The lines are really long in some browsers (chrome, IE). Also see my comments for SUBSTATE problem.

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