문제
농부 존은 N( 2 <= N <=20)마리의 암소를 소유하고 있는데 각 i번째 암소는 M[i]만큼의 우유를 매일 생산한다.
( 1 <= M[i] <= 100,000,000)
농부 존은 우유 생산량을 늘이기 위해 유축기를 구입했다.
그런데 이 유축기는 균형잡힌 암소 그룹에 대해서만 우유를 짤 수 있다.
그래서 농부 존은 자신의 암소들 중 일부를 골라 균형잡힌 부분집합을 만든다.
어떤 암소들이 균형잡힌 부분집합이 되려면 그 집합을 생산량이 같도록 두 그룹으로 분할 할 수 있어야 한다.
농부 존은 균형잡인 부분집합이 얼마나 되는지 알아보려 한다.
농부 존을 위하여 이를 구하는 프로그램을 작성하시오.
[예제 설명]
다음과 같이 3가지가 가능하다.
subset {1, 2, 3} 에 대하여 {1, 2}, {3}이 가능하고,
subset {1, 3, 4} 에 대하여 {1, 3}, {4}가 가능하며,
subset {1, 2, 3, 4}에 대하여 {1, 4}, {2, 3}이 된다.
입력
첫 행에 암소의 수 N이 주어진다. ( 2 <= N <= 20)
두 번째 행부터 N마리 소들이 생산하는 우유의 양 M[i]가 입력된다. ( 1 <= M[i] <= 100,000,000)
출력
균형잡인 부분집합의 수를 출력한다.
예제
4
1
2
3
4
3
힌트
출처
usaco 2012 US open, Gold 3
로그인해야 코드를 작성할 수 있어요.