균형 잡힌 소 부분집합

시간 제한1초메모리 제한128 MB

요약

소가 최대 20마리일 때, 두 그룹의 우유 생산량 합이 같아지도록 나눌 수 있는 부분집합의 수를 구한다.

문제

축산업자 John은 소 $N$ 마리를 기르고 있으며 ( $2 \le N \le 20$ ), $i$ 번 소는 하루에 우유를 $M(i)$ 단위 생산한다 ( $1 \le M(i) \le 10^8$ ).

John은 새 착유기를 헛간에 설치했는데, 이 기계는 헛간 왼쪽에 있는 소들의 우유 생산량 총합이 오른쪽에 있는 소들의 총합과 정확히 같을 때만 정상 작동한다.

소들의 부분집합을 두 그룹으로 나누어 각 그룹의 우유 생산량 총합을 같게 만들 수 있으면, 그 부분집합을 균형 잡힌(balanced) 부분집합이라고 하자. $N$ 마리 소의 부분집합 중 균형 잡힌 것이 몇 개인지 구하여라.

첫째 줄에 정수 $N$ 이 주어진다.

다음 $N$ 개의 줄 중 $i+1$ 번째 줄에는 $M(i)$ 가 주어진다.

균형 잡힌 소 부분집합의 개수를 한 줄에 출력한다.